Logo Passei Direto
Buscar

Teoria da Computação

Outros
Considere a seguinte gramática: G = {S, (0, 1, c), (S→0S0, S→1S1, S→c), S}. Assinale a alternativa que contém, apenas, cadeias geradas por essa gramática.


00c00, 1100011, 00100, c
0c0, 110c111, 001c100, c
00c1, 001c100, 00c10, c
0c0, 11c11, 001c100, c
00c10, 11c11, 01c11, c
User badge image
Progresso com Exercícios

há 2 anos

User badge image
Progresso com Exercícios

há 2 anos

AV_TEORIA_DA_COMPUTAÇÃO
4 pág.

AV_TEORIA_DA_COMPUTAÇÃO

ESTÁCIO EAD

Respostas

User badge image

Ed Verified user icon

há 2 anos

A alternativa que contém apenas cadeias geradas pela gramática G é: c Explicação: A gramática G possui três regras de produção: - S → 0S0 - S → 1S1 - S → c A partir dessas regras, podemos gerar as seguintes cadeias: - c (usando a regra S → c) As demais cadeias apresentadas na pergunta não podem ser geradas pela gramática G, pois contêm símbolos que não pertencem ao alfabeto da gramática (0, 1 e c).

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

AV_TEORIA_DA_COMPUTAÇÃO
4 pág.

AV_TEORIA_DA_COMPUTAÇÃO

ESTÁCIO EAD

Mais perguntas desse material

Seja G = (V, T, P, E), onde V = {+, *, (, ), id, T, F, E}, T = {+, *, (, ), id} e P:

1. E → E + T 4. T → F
2. E → T 5. F → (E)
3. T → T * F 6. F → id

Os símbolos E, T, F são abreviaturas para expressão, termo e fator, respectivamente e id é um identi cador válido dessa linguagem.

Assinale a alternativa que tem uma derivação correta para a expressão id + (id * id):
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id / (id - id).
E =>1 E + T =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F * F) =>6 id + (id * id).
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
E =>1 E + T =>3 E + T * F =>5 E + T * (E) =>1 E + T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>4 (F + F*F) =>6 (id + id *id).


T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id + (id * id).
E =>1 E + T =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F * F) =>6 id + (id * id).
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
E =>1 E + T =>3 E + T * F =>5 E + T * (E) =>1 E + T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>4 (F + F*F) =>6 (id + id *id).

Considere o autômato finito mostrado na figura abaixo (os círculos concêntricos representam estado final) e assinale a afirmativa correta.


A palavra 10101 é reconhecida pelo autômato.
A palavra 01010 não é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
A palavra vazia não é reconhecida pelo autômato.
A palavra 101 é reconhecida pelo autômato.

Qual é a linguagem da gramática com as seguintes regras de produção: S → ASb | c, A → a?


{acbn|n ∈ N}
{ancnb|n ∈ N}
{acnb|n ∈ N}
{ancbn|n ∈ N}
{ancb|n ∈ N}

Seja o autômato finito mostrado na figura abaixo que opera sobre o alfabeto Σ = {a,b} (o círculo em negrito indica um estado terminal): Analise as seguintes afirmativas. I. O autômato finito mostrado na figura é determinístico. II. O autômato finito mostrado na figura é não-determinístico. III. O autômato finito mostrado na figura reconhece a palavra vazia. A análise permite concluir que


Somente as afirmativas I e II são falsas.
Somente a afirmativa II é falsa.
Somente a afirmativa III é falsa.
Somente a afirmativa I é falsa.
Somente as afirmativas II e III são falsas.

Considere a seguinte gramática G, onde S é o símbolo inicial: S → AcB, A → cA | aB, B → cB | aA, A → λ. Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.


aaca
aa
aaaca
ccac
ccca

Mais conteúdos dessa disciplina