Equivalência ACPND-GLC

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

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.

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:

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

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

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

Para cada uma das regras de uma gramática livre de contexto G apresentadas a seguir, indique qual das alternativas representa corretamente a regra de transição que ela gera durante a criação do ACPND equivalente a G (considere a notação abreviada). Para a regra C->aBB: [blank_start]<C, a, BB>[blank_end] Para a regra C->b: [blank_start]<C, b, B>[blank_end] Para a regra C->λ: [blank_start]<C, λ, C>[blank_end]

Para cada uma das regras de transição de um ACPND M apresentadas a seguir, indique qual das alternativas representa corretamente a regra que ela gera durante a criação do gramática G equivalente a M (novamente, utilizamos a notação abreviada). Para a regra <x, Y, Z> [blank_start]Y->xZ[blank_end] Para a regra <λ, Z, λ> [blank_start]λ->Zλ[blank_end] Para a regra <y, Y, λ> [blank_start]y->Y[blank_end]

Considere o ACPND da figura. Qual das gramáticas a seguir representa a gramática equivalente a este ACPND?

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.