Linguagem Formais

Linguagens Formais - Complementos
Hipótese de Church

“A capacidade de computação representada pela Máquina de Turing é o limite máximo que pode ser atingido por qualquer dispositivo de computação”
A Hierarquia de Chomsky
Linguagens Enumeráveis Recursivamente (ou Tipo 0)
Linguagens Sensíveis ao Contexto (ou Tipo 1)
Linguagens Livres de Contexto (ou Tipo 2)
Linguagens Regulares (ou Tipo 3)

As linguagens formais podem ser vistas a partir de dois aspectos principais:
a) O formalismo responsável pela sua geração
b) O dispositivo reconhecedor da linguagem
Linguagens Regulares (ou Tipo 3)
São linguagens compostas apenas por expressões regulares. O formalismo gerador nas linguagens regulares é chamado de Gramática Regular. O dispositivo reconhecedor de uma linguagem regular é o
Autômato Finito.
Linguagens Livres de Contexto (ou Tipo 2)
São definidas a partir das Gramáticas Livres de Contexto. Uma Gramática Livre de Contexto G é uma gramática G = (V, T, P, S) com a restrição de que qualquer regra de produção de P é da forma A ⇒ α, onde: a) A é uma variável de V
b) α é uma palavra de (V ∪ T)*
O dispositivo reconhecedor é o Autômato com Pilha.
Linguagens Sensíveis ao Contexto (ou Tipo 1)
São definidas a partir das Gramáticas Sensíveis ao Contexto. Uma Gramática Sensível ao Contexto G é uma gramática G = (V, T, P, S) com a restrição de que qualquer regra de produção de P é da forma α
⇒ β, onde:
a) α é uma palavra de (V ∪ T)+
b) β é uma palavra de (V ∪ T)*
c) |α| ≤ |β|, excetuando-se, eventualmente, para S ⇒ ε. Neste caso, S não pode estar presente no lado direito de qualquer produção.
Linguagens Enumeráveis Recursivamente (ou Tipo 0)

São as linguagens aceitas por uma Máquina de Turing. Formam o conjunto de todas as linguagens que podem ser reconhecidas (“compiladas”) mecanicamente. Assim, é possível estipular que para uma Máquina de Turing M:
ACEITA(M) ∪ REJEITA(M) ∪ LOOP(M) = Σ*
Linguagens Recursivas

São um subconjunto das