Qual dos seguintes conjuntos de produções está na forma normal de Greibach?

• S→aA, A→aAA|a

• S→aA|λ, A→Aa, A→a

• S→Aa, A→aA, A→A|λ, A→a

Qual das alternativas indica corretamente o formato das produções na forma normal de Greibach? onde a, b, c ∈ Vn e A, B, C ∈ Vt.

• A→BA, A→a, B→b

• A→ABc|c, A→Bc, B→b

• A→aB, A→a

Seja G uma gramática livre de contexto. Então pode se dizer que ela está na forma normal de Greibach quando as produções:

• Possuem recursões à esquerda.

• Não possuem recursões à esquerda.

• Tiverem pelo menos um S→λ.

O Teorema da equivalência estabelece que as linguagens aceitas por ACPNDs são precisamente as linguagens livres de contexto. Esta afirmação é verdadeira?

• Sim

• Não

Toda Linguagem Livre de Contexto é aceita por algum ACP determinístico?

• Sim

• Não

A seguinte afirmação está correta?
“Toda Linguagem Livre de Contexto é aceita por algum ACPND de um estado?”

• Sim

• Não

Considere o seguinte conjunto de regras de produção de uma Gramática G:
S → aA,
A → aABC | bB | a
B → b,
C → c.

Qual dos ACPs a seguir é equivalente a esta linguagem.