Alternativa C - Linguagem Livre de Contexto → Autômato de Pilha
A questão aborda a Hierarquia de Chomsky, um modelo fundamental em Teoria da Computação que classifica as linguagens formais de acordo com a complexidade de suas gramáticas e os autômatos capazes de reconhecê-las.
Hierarquia de Chomsky
Para responder corretamente, é necessário memorizar ou consultar a correspondência entre os tipos de linguagens e seus respectivos autômatos definidores:
| Tipo | Linguagem | Gramática | Autômato Correspondente |
|---|
| 0 | Recursivamente Enumerável | Irrestrita | Máquina de Turing |
| 1 | Sensível ao Contexto | Sensível ao Contexto | Autômato Limitado Linear |
| 2 | Livre de Contexto | Livre de Contexto | Autômato de Pilha |
| 3 | Regular | Regular | Autômato Finito |
Análise das Alternativas
Vamos verificar cada uma das opções apresentadas no enunciado com base na tabela acima:
- Linguagem Regular → Máquina de Turing: Incorreto. Linguagens Regulares (Tipo 3) são reconhecidas por Autômatos Finitos. Embora uma Máquina de Turing possa simular um autômato finito, a definição padrão associa Regular a Autômato Finito.
- Linguagem Recursivamente Enumerável → Autômato de Pilha: Incorreto. Linguagens Recursivamente Enumeráveis (Tipo 0) exigem uma Máquina de Turing. O Autômato de Pilha reconhece linguagens do Tipo 2.
- Linguagem Livre de Contexto → Autômato de Pilha: Correto. As linguagens livres de contexto (Tipo 2), como muitas sintaxes de programação, são geradas por gramáticas livres de contexto e reconhecidas por autômatos de pilha (que possuem uma memória auxiliar ilimitada em forma de pilha).
- Linguagem Regular → Máquina de Turing com fita limitada: Incorreto. Uma Máquina de Turing com fita limitada (Autômato Limitado Linear) corresponde às linguagens do Tipo 1 (Sensíveis ao Contexto).
- Linguagem Sensível ao Contexto → Autômato Finito: Incorreto. Linguagens Sensíveis ao Contexto (Tipo 1) requerem mais poder computacional do que um Autômato Finito. Elas são reconhecidas pelo Autômato Limitado Linear.
Conclusão
A única relação correta estabelecida pela teoria dos autômatos e formalismos linguísticos é a que associa a classe de linguagens livres de contexto ao autômato de pilha.
Portanto, a alternativa correta é a C.