LFA - Automato Finito Determinado

Texto – Gramática de Noam Chomsky

A Hierarquia de Chomksy é definida em 4 (quatro) níveis: Tipo – 0 ou Linguagem de Estrutura de Frase; Tipo – 1 ou Livres de Contexto; Tipo – 2 ou Sensíveis ao Contexto; e por fim, mas não menos importante, as Linguagens Regulares.

Caracterizando as diferentes linguagens:

1. Tipo – 0: linguagens do tipo 0, são linguagens a que não foram impostas nenhum tipo de limitação, as mesmas são capazes de gerar linguagens recursivamente enumeráveis, por isso também podem ser conhecidas por este nome.

É uma gramática formal, descrita por G = (N, ∑, P, S). Dentre as outras gramáticas, esta é a que possui o maior nível de liberdade em suas regras, e conforme aumentamos o nível, aumentamos também as restrições de suas respectivas regras. A gramática de Estrutura de Fase é reconhecida pela máquina de Turing.

• Regra de Produção:

α 🡪 β

 α ꞓ ( V+T) * V (V + T) *;  β ꞓ (V + T)*.

V: Variáveis e

T: Terminais.

1. Tipo – 1: As gramáticas sensíveis ao contexto são compostas por aquelas gramáticas que se às regras de substituição foram impostas a restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada. Como o próprio nome diz “Hierarquia de Chomsky”, ou seja, toda gramática do tipo n-1, terá como herança as regras da gramática do tipo (n-1) -1.

1. Tipo – 2: seus reconhecedores são autômatos pilha.

Regra de Produção:

A 🡪 α, onde α ꞓ (T U V) *.

Onde A existe um único não terminal e α qualquer combinação de terminais e não terminais.

1. Tipo – 3: seus reconhecedores são autômatos finitos, sua linguagem é um conjunto de palavras cuja correção sintática só necessita de memória em quantidade finita numa leitura da esquerda para a direita. Outra caracterização desta linguagem, é que a estrutura desta segue um padrão (estrutura regular), por isso denominada de Linguagem Regular.

,

...