Questão de TI - Desenvolvimento de Sistemas — Linguagens Formais, Autômatos e Expressões Regulares (Regex) — FUNDATEC 2025

Linguagens livres de contexto e autômatos com pilha

Gabarito: letra A — a sequência correta é V – V – V – V – F. As quatro primeiras assertivas descrevem corretamente propriedades fundamentais das gramáticas livres de contexto (derivações à esquerda/direita e árvores de derivação, definição de ambiguidade, transformação para a Forma Normal de Chomsky) e a equivalência entre essas linguagens e os autômatos com pilha; apenas a última é falsa, pois a simplificação de uma gramática, ao remover símbolos inúteis e inacessíveis, não altera a linguagem gerada.

Para entender por que a resposta é essa, é preciso dominar alguns conceitos centrais da teoria das linguagens formais. Uma gramática livre de contexto (GLC) é um sistema de reescrita composto por um conjunto de variáveis (não terminais), um alfabeto de terminais, uma variável inicial e um conjunto de produções da forma $A \rightarrow \alpha$, onde $A$ é uma variável e $\alpha$ é uma cadeia de terminais e/ou variáveis. A partir da variável inicial, aplicamos as produções para gerar cadeias de terminais — o conjunto de todas as cadeias assim geradas é a linguagem gerada pela gramática.

Uma derivação é a sequência de substituições que leva da variável inicial até uma cadeia de terminais. Quando, em cada passo, substituímos sempre a variável mais à esquerda, temos uma derivação à esquerda; quando substituímos sempre a mais à direita, uma derivação à direita. Para uma mesma cadeia, essas duas derivações podem produzir árvores de derivação diferentes — e é exatamente essa possibilidade que caracteriza a ambiguidade. Uma gramática é ambígua quando existe pelo menos uma cadeia que possui duas ou mais árvores de derivação distintas (ou, equivalentemente, duas derivações à esquerda ou duas à direita diferentes).

A Forma Normal de Chomsky (FNC) é uma forma restrita de gramática livre de contexto em que toda produção tem uma das duas formas: $A \rightarrow BC$ (duas variáveis) ou $A \rightarrow a$ (um terminal). O teorema fundamental afirma que toda gramática livre de contexto que não gere a cadeia vazia pode ser transformada em uma gramática equivalente na FNC, ou seja, que gera exatamente a mesma linguagem. Essa transformação envolve eliminar produções vazias, produções unitárias e símbolos inúteis, e então reescrever as produções restantes na forma restrita.

A relação entre linguagens livres de contexto e autômatos é um dos resultados mais importantes da teoria da computação: uma linguagem é livre de contexto se, e somente se, existe um autômato com pilha (AP) que a aceita. O autômato com pilha é um modelo computacional com uma fita de entrada e uma pilha (memória ilimitada, mas com acesso apenas ao topo). Existem dois critérios de aceitação equivalentes: por estado final (quando o autômato entra em um estado de aceitação após consumir toda a entrada) e por pilha vazia (quando a pilha fica vazia após consumir toda a entrada). A equivalência entre esses dois critérios é um teorema clássico: para toda linguagem aceita por um AP por estado final, existe um AP que a aceita por pilha vazia, e vice-versa. Portanto, a afirmação de que "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" é verdadeira — a ressalva "desde que" é desnecessária, pois a aceitação por pilha vazia é suficiente para reconhecer toda a classe.

A simplificação de uma gramática é o processo de eliminar produções e símbolos que não contribuem para a geração da linguagem. Isso inclui a remoção de símbolos inúteis (aqueles que não aparecem em nenhuma derivação de uma cadeia terminal) e símbolos inacessíveis (aqueles que não podem ser alcançados a partir da variável inicial). O ponto crucial é que essas remoções são feitas de forma a preservar exatamente a linguagem gerada: nenhuma cadeia é adicionada ou removida. Portanto, a afirmação de que a simplificação "pode alterar a linguagem gerada" é falsa — a simplificação, por definição, mantém a linguagem intacta.

A pegadinha desta questão está na última assertiva: o candidato pode pensar que remover símbolos inúteis ou inacessíveis "muda" a gramática e, portanto, a linguagem. Mas a teoria garante que a simplificação é uma transformação de equivalência: a gramática simplificada gera exatamente a mesma linguagem que a original. É essa distinção entre "mudar a gramática" e "mudar a linguagem" que separa o certo do errado.

Assertiva 1 — ✅ Verdadeira

A afirmação está correta. Em uma gramática livre de contexto, as derivações à esquerda e à direita de uma mesma cadeia podem resultar em árvores de derivação diferentes. Isso ocorre quando a gramática é ambígua: para uma mesma cadeia, existem duas ou mais derivações à esquerda (ou à direita) distintas, que correspondem a árvores de derivação diferentes. Por exemplo, na gramática $S \rightarrow S + S \mid S * S \mid a$, a cadeia $a + a * a$ pode ser derivada de duas maneiras diferentes, gerando árvores distintas. A palavra-chave é "podem": não é obrigatório que resultem em árvores diferentes, mas é possível.

Assertiva 2 — ✅ Verdadeira

A afirmação está correta. A definição formal de gramática ambígua é exatamente essa: existe ao menos uma cadeia que possui duas ou mais árvores de derivação distintas. Essa é a definição canônica adotada na teoria das linguagens formais. Uma gramática que não é ambígua é chamada de não ambígua — para toda cadeia gerada, existe uma única árvore de derivação (e, portanto, uma única derivação à esquerda e uma única à direita).

Assertiva 3 — ✅ Verdadeira

A afirmação está correta. O teorema da Forma Normal de Chomsky estabelece que toda gramática livre de contexto (que não gere a cadeia vazia) pode ser transformada em uma gramática equivalente na FNC, ou seja, que gera exatamente a mesma linguagem. A transformação envolve etapas como eliminação de produções vazias, produções unitárias e símbolos inúteis, e a reescrita das produções na forma $A \rightarrow BC$ ou $A \rightarrow a$. A ressalva sobre a cadeia vazia é um detalhe técnico: se a linguagem contém a cadeia vazia, a gramática na FNC pode incluir uma produção especial $S \rightarrow \varepsilon$, mas isso não invalida o teorema para a classe geral.

Assertiva 4 — ✅ Verdadeira

A afirmação está correta. O teorema fundamental da equivalência entre linguagens livres de contexto e autômatos com pilha afirma que uma linguagem é livre de contexto se, e somente se, existe um autômato com pilha que a aceita. Além disso, os critérios de aceitação por estado final e por pilha vazia são equivalentes: para todo AP que aceita por estado final, existe um AP que aceita por pilha vazia (e vice-versa). Portanto, toda linguagem livre de contexto pode ser aceita por um AP usando o critério de pilha vazia. A ressalva "desde que ele use o critério de aceitação por pilha vazia" é desnecessária, mas não torna a afirmação falsa — ela apenas enfatiza um dos critérios possíveis.

Assertiva 5 — ❌ Falsa

A afirmação está incorreta. A simplificação de uma gramática, que envolve a remoção de símbolos inúteis (que não aparecem em nenhuma derivação de cadeia terminal) e símbolos inacessíveis (que não podem ser alcançados a partir da variável inicial), é feita de forma a preservar exatamente a linguagem gerada. Nenhuma cadeia é adicionada ou removida durante o processo. Portanto, a simplificação não altera a linguagem gerada — ela apenas remove elementos que não contribuem para a geração de cadeias. A pegadinha está em confundir "mudar a gramática" com "mudar a linguagem": a gramática muda (fica mais enxuta), mas a linguagem permanece idêntica.

Gabarito: letra A — V – V – V – V – F.