Quiz
Equivalência ACPND-GLC
This quiz has question types that open in the usual player.
Questions in this quiz (10)
1Qual dos seguintes conjuntos de produções está na forma normal de Greibach?
- AS→aA, A→aAA|a
- BS→aA|λ, A→Aa, A→a
- CS→Aa, A→aA, A→A|λ, A→a
2Qual das alternativas indica corretamente o formato das produções na forma normal de Greibach? onde a, b, c ∈ Vn e A, B, C ∈ Vt.
- AA→BA, A→a, B→b
- BA→ABc|c, A→Bc, B→b
- CA→aB, A→a
3Seja G uma gramática livre de contexto. Então pode se dizer que ela está na forma normal de Greibach quando as produções:
- APossuem recursões à esquerda.
- BNão possuem recursões à esquerda.
- CTiverem pelo menos um S→λ.
4O Teorema da equivalência estabelece que as linguagens aceitas por ACPNDs são precisamente as linguagens livres de contexto. Esta afirmação é verdadeira?
- ASim
- BNão
5Toda Linguagem Livre de Contexto é aceita por algum ACP determinístico?
- ASim
- BNão
6A seguinte afirmação está correta?
“Toda Linguagem Livre de Contexto é aceita por algum ACPND de um estado?”- ASim
- BNão
7Para 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]- A<C, a, BB>
- B<a, C, BB>
- C<C, a, B>
- D<B, a, C>
- E<C, b, B>
- F<b, C, B>
- G<C, λ, b>
- H<b, C, λ>
- I<C, λ, C>
- J<λ, C, C>
- K<λ, C, λ>
- L<C, λ, λ>
8Para 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]- AY->xZ
- Bx->YZ
- CY->Zx
- DZ->xY
- Eλ->Zλ
- FZ->Z
- GZ->λ
- Hλ->Z
- Iy->Y
- Jy->λ
- KY->λ
- LY->y
9Considere o ACPND da figura. Qual das gramáticas a seguir representa a gramática equivalente a este ACPND?
- AG = ({i, e}, {Z}, P, Z), P = { Z → iZ | λ | Z→eZZ | e }
- BG = ({i, e}, {Z}, P, Z), P = {Z → iZZ | e | λ}
- CG = ({i, e}, {Z}, P, Z), P = {Z → iZZ | e }
- DG = ({i, e}, {Z}, P, Z), P = {Z → iZ | e | λ}
10Considere 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.- A
- B
- C
- A
Information
- Description
- Teste seus conhecimentos relacionados ao teorema da equivalência entre Autômatos com Pilha Não-Determinísticos e Gramáticas Livres de Contexto.
- Author
- Darlan Santana F
- Language
- Português
- Views
- 75
- Tags
- Rating
- No ratings yet Rate this quiz