Turmas - 2º Semestre de 2026(Poscomp, 2025) Sobre linguagens e gramáticas livres de contexto e autômatos com pilha, analise as assertivas abaixo e assinale V, se verdadeiras, ou F, se falsas.
( ) Em uma gramática livre de contexto, as derivações à esquerda e à direita de uma mesma cadeia podem resultar em diferentes árvores de derivação.
( ) Uma gramática é dita ambígua se existir ao menos uma cadeia que tenha duas ou mais árvores de derivação distintas.
( ) A classe LL(1) não aceita linguagens com produções que apresentem recursões diretas à esquerda (ex. L→La), mas aceita linguagens com recursões indiretas (ex. L→Ra, R→Lb).
( ) Toda linguagem livre de contexto pode ser aceita por um autômato com pilha, desde que ele use o critério de aceitação por pilha vazia.
( ) A simplificação de uma gramática pode alterar a linguagem gerada, pois remove símbolos inúteis e símbolos inacessíveis.
A ordem correta de preenchimento dos parênteses, de cima para baixo, é:
a. V – V – F – V – F.
b. F – V – F – F – F.
c. V – F – V – F – V.
d. V – F – F – V – V.
e. F – F – V – F – V.
Vamos realizar a análise detalhada de cada assertiva, com a respectiva classificação e a justificativa teórica:
(V) Em uma gramática livre de contexto, as derivações à esquerda e à direita de uma mesma cadeia podem resultar em diferentes árvores de derivação.
Se a gramática for ambígua, uma mesma cadeia pertencente à linguagem terá duas ou mais árvores de derivação distintas. Consequentemente, ela terá múltiplas derivações à esquerda e múltiplas derivações à direita. Ao pegarmos uma derivação à esquerda (que gera a Árvore 1) e uma derivação à direita (que gera a Árvore 2) para essa mesma cadeia, elas resultarão em árvores diferentes.
Observação: se a gramática fosse não-ambígua, a cadeia teria apenas uma árvore, e suas derivações à esquerda e à direita obrigatoriamente resultariam nessa mesma árvore.
(V) Uma gramática é dita ambígua se existir ao menos uma cadeia que tenha duas ou mais árvores de derivação distintas.
Esta é a definição clássica e exata de ambiguidade em Linguagens Formais e Autômatos. Uma gramática é ambígua se, e somente se, existir pelo menos uma cadeia válida que possa ser gerada por mais de uma árvore de derivação (ou, equivalentemente, por mais de uma derivação mais à esquerda ou mais à direita).
(F) A classe LL(1) não aceita linguagens com produções que apresentem recursões diretas à esquerda (ex. L→La), mas aceita linguagens com recursões indiretas (ex. L→Ra, R→Lb).
Analisadores descendentes (top-down), como os da classe LL(1), não conseguem lidar com nenhum tipo de recursão à esquerda, seja ela direta ou indireta. A presença de recursão à esquerda (em qualquer de suas formas) faria com que o analisador entrasse em um loop infinito, tentando expandir o mesmo não terminal repetidamente sem consumir nenhum símbolo de entrada da cadeia.
(V) Toda linguagem livre de contexto pode ser aceita por um autômato com pilha, desde que ele use o critério de aceitação por pilha vazia.
Toda linguagem livre de contexto pode ser reconhecida por um autômato com pilha. A equivalência clássica entre gramáticas livres de contexto e autômatos com pilha permite usar o critério de aceitação por pilha vazia.
(F) A simplificação de uma gramática pode alterar a linguagem gerada, pois remove símbolos inúteis e símbolos inacessíveis.
O objetivo central dos algoritmos de simplificação de gramáticas (remoção de produções vazias, produções da forma A→B e símbolos inúteis) é produzir uma gramática estritamente equivalente à original. A gramática simplificada gerará exatamente a mesma linguagem (L(G) = L(G')), apenas sem símbolos e regras que nunca contribuem para a geração de cadeias de terminais.
Conforme exposto, a resposta correta é:
a. V – V – F – V – F.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 