Equivalência ACPND-GLC

Question 1

Question

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

Answer

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

Question 2

Question

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.

Answer

A→BA, A→a, B→b
A→ABc|c, A→Bc, B→b
A→aB, A→a

Question 3

Question

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:

Answer

Possuem recursões à esquerda.
Não possuem recursões à esquerda.
Tiverem pelo menos um S→λ.

Question 4

Question

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

Answer

Sim
Não

Question 5

Question

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

Answer

Sim
Não

Question 6

Question

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

Answer

Sim
Não

Question 7

Question

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]

Answer

<C, a, BB>
<a, C, BB>
<C, a, B>
<B, a, C>
<C, b, B>
<b, C, B>
<C, λ, b>
<b, C, λ>
<C, λ, C>
<λ, C, C>
<λ, C, λ>
<C, λ, λ>

Question 8

Question

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]

Answer

Y->xZ
x->YZ
Y->Zx
Z->xY
λ->Zλ
Z->Z
Z->λ
λ->Z
y->Y
y->λ
Y->λ
Y->y

Question 9

Question

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

Image:

58fba617-b416-4587-9c0b-a4bb3bf9876f (image/png)

Answer

G = ({i, e}, {Z}, P, Z), P = { Z → iZ | λ | Z→eZZ | e }
G = ({i, e}, {Z}, P, Z), P = {Z → iZZ | e | λ}
G = ({i, e}, {Z}, P, Z), P = {Z → iZZ | e }
G = ({i, e}, {Z}, P, Z), P = {Z → iZ | e | λ}

Question 10

Question

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.

Answer

Next up

Equivalência ACPND-GLC

Description

Resource summary

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Similar

	Created by Darlan Santana F about 9 years ago