Equivalência ACPND-GLC

Pregunta 1 de 10

1

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

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 2 de 10

1

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.

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 3 de 10

1

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:

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 4 de 10

1

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

Selecciona una de las siguientes respuestas posibles:

Sim
Não

Explicación

Pregunta 5 de 10

1

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

Selecciona una de las siguientes respuestas posibles:

Sim
Não

Explicación

Pregunta 6 de 10

1

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

Selecciona una de las siguientes respuestas posibles:

Sim
Não

Explicación

Pregunta 7 de 10

1

Selecciona la opción correcta de los menús desplegables para completar el texto.

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:
( <C, a, BB>, <a, C, BB>, <C, a, B>, <B, a, C> )

Para a regra C->b:
( <C, b, B>, <b, C, B>, <C, λ, b>, <b, C, λ> )

Para a regra C->λ:
( <C, λ, C>, <λ, C, C>, <λ, C, λ>, <C, λ, λ> )

Explicación

Pregunta 8 de 10

1

Selecciona la opción correcta de los menús desplegables para completar el texto.

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>
( Y->xZ, x->YZ, Y->Zx, Z->xY )

Para a regra <λ, Z, λ>
( λ->Zλ, Z->Z, Z->λ, λ->Z )

Para a regra <y, Y, λ>
( y->Y, y->λ, Y->λ, Y->y )

Explicación

Pregunta 9 de 10

1

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

Selecciona una de las siguientes respuestas posibles:

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 | λ}

Explicación

Pregunta 10 de 10

1

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.

	Creado por Darlan Santana F hace más de 8 años

Teste seus conhecimentos relacionados ao teorema da equivalência entre Autômatos com Pilha Não-Determinísticos e Gramáticas Livres de Contexto.

Equivalência ACPND-GLC

Pregunta 1 de 10

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 2 de 10

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.

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 3 de 10

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:

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 4 de 10

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 5 de 10

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 6 de 10

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 7 de 10

Selecciona la opción correcta de los menús desplegables para completar el texto.

Explicación

Pregunta 8 de 10

Selecciona la opción correcta de los menús desplegables para completar el texto.

Explicación

Pregunta 9 de 10

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

Selecciona una de las siguientes respuestas posibles:

Explicación

Pregunta 10 de 10

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.

Selecciona una de las siguientes respuestas posibles:

Explicación

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

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.