Turmas - 2º Semestre de 2025(Poscomp, 2022) Dada a gramática G = ({S}, {(, )}, P, S), em que P = {S → (S) S | ε}, identifique o reconhecedor para a linguagem gerada por G, que possua a menor complexidade.
a. Expressão Regular.
b. Autômato Finito.
c. Autômato de Pilha.
d. Máquina de Turing com Fita Limitada.
e. Máquina de Turing.
| Tipo | Gramática | Linguagem | Reconhecedor |
|---|---|---|---|
| 0 | Irrestrita | Recursivamente Enumeráveis | Máquina de Turing |
| 1 | Sensível ao Contexto | Sensíveis ao Contexto | Máquina de Turing com fita limitada |
| 2 | Livre de Contexto | Livres de Contexto | Autômato de Pilha |
| 3 | Linear | Regulares | Autômato Finito |
a. Expressão Regular.
b. Autômato Finito.
c. Autômato de Pilha.
d. Máquina de Turing com Fita Limitada.
e. Máquina de Turing.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 