Trabalho Hierarquia De Chomsky

Trabalho Hierarquia de Chomsky
Abel Fabiane
Gabriel Ricardo
Hierarquia de Chomsky:
Noam Chomsky descreveu uma classificação de gramáticas em 1959, denominando Hierarquia de Chomsky, classificação esta que possuí 4 níveis indo do 0, menos restrito, até o 3, mais restrito. Cada próximo nível pertence ao nível anterior também, ou seja, o nível “n” sempre pertence a “n-1”. Ela pode ser estudada separadamente por linguagens, gramática e autômatos. Esta hierarquia pode ser exemplificada visualmente assim:

Linguagens:
Regular: Aquela que pode ser expressa por expressões regulares e pertence ao nível 3 na hierarquia. Conjunto de palavras que necessita apenas de memória finita para ser corrigida sintaticamente e a estrutura delas segue um padrão. Todas linguagens finitas são regulares e podem ser reconhecidas por autómatos de estados finitos.
Exemplo: L = {ε} = Ø*, que representa uma linguagem composta por apenas uma cadeia vazia.

Livre de Contexto: Conjunto de palavras que podem ter seus padrões estruturais sequencializados. Pertence ao nível 2 na hierarquia, é gerada por alguma gramática livre de contexto e é reconhecida por autômatos com pilha.
Exemplo: L = {anbn : n ≥ 1}, que representa todas as cadeias de caracteres não vazias de tamanho par com a primeira parte sempre preenchida com “a”s e a segunda preenchida com “b”s.

Sensível ao Contexto: Difícil de descrever formalmente e pode conter padrões que dependam de outros já ocorridos. Pertence ao nível 1 na hierarquia, é equivalente a uma máquina de Turing não determinística linearmente limitada e é reconhecida por autômatos lineares limitados.
Exemplo: L = {anbncn : n ≥ 1}, que é a linguagem de todas as cadeias consistindo em n ocorrências do símbolo “a”, e n “b”s, e n “c”s.

Recursivamente Enumerável (Decidível): Conjunto de palavras que podem ser reconhecidas por um algoritmo, pertence ao nível 0 na hierarquia e pode ser reconhecida por máquinas de Turing.
Exemplo: Uma palavra x ∈ Σ que é aceita por uma máquina