Hierarquia chomsky

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1550 palavras )
  • Download(s) : 0
  • Publicado : 2 de abril de 2012
Ler documento completo
Amostra do texto
HIERARQUIA DE CHOMSKY

Professor Carlos Hairon

 Noam Chomsky


Nasceu em 7 de dezembro de 1928, na Filadélfia



Avram Noam Chomsky é um linguista, filósofo e ativista político estadunidense



Professor de Linguística no Instituto de Tecnologia de Massachusetts



Autor de trabalhos fundamentais sobre as propriedades matemáticas das
linguagens formais

•Hierarquia de Chomsky (1959):
o Chomsky é famoso por pesquisar vários tipos de
linguagens formais procurando entender se poderiam ser
capazes de capturar as propriedades -chave das línguas
humanas

 A hierarquia de Chomsky


Divide as gramáticas formais em classes com poder expressivo crescente, por
exemplo, cada classe sucessiva pode gerar um conjunto mais amplo de
linguagens formais que aclasse imediatamente anterior.



Classificação de gramáticas formais que possui 4 níveis (Tipos 0, 1, 2 e 3)



Os níveis 2 e 3 são amplamente utilizados na descrição de linguagem de
programação e na implementação de interpretadores e compiladores:
o O nível 2 é utilizado em análise sintática (computação)
o O nível 3 em análise léxica



A classificação das gramáticas começa pelotipo 0, com maior nível de
liberdade em suas regras, e aumentam as restrições até o tipo 3



Cada nível é um superconjunto do próximo

 A hierarquia de Chomsky


As quatro classes de
linguagens e suas
inclusões próprias
constituem a
Hierarquia de
Chomsky

 Linguagens enumeráveis recursivamente (Tipo 0):


Tipo de linguagem formal, também conhecida como Turing-reconhecível



Definições de linguagens enumeráveis recursivamente formais:

o É um subconjunto recursivamente enumerável no conjunto de todas as
palavras possíveis sob o alfabeto da linguagem;
o É uma linguagem formal para a qual existe uma máquina de Turing que irá
enumerar todas as cadeias válidas da linguagem;
o Uma linguagem recursivamente enumerável é uma linguagem formal para
a qualexiste uma máquina de Turing que irá parar e aceitar quando se
roda com qualquer cadeia da linguagem na entrada e pode parar e rejeitar
ou entrar em loop quando se roda com qualquer cadeia que não é da
linguagem.

 Linguagens enumeráveis recursivamente (Tipo 0):


GRAMÁTICA IRRESTRITA (OU GRAMÁTICA COM ESTRUTURA DE FRASE):
o Nenhuma restrição é imposta

o O universo das linguagens quese podem definir através dos mecanismos
gerativos definidos pela gramática corresponde exatamente ao conjunto
das linguagens que esta classe de gramática é capaz de gerar
o Todo o universo das linguagens é gerado por gramáticas deste tipo

o Exemplo de gramática irrestrita para a linguagem L = { anb2nan / n >= 1 }:
G = ( {A, B, S}, {a, b}, P, S )
P={
S  aAbba
aAb  aabbbA | ab
bAb  bbAbAa  Bbaa
b B  Bb
aB  aA }


MÁQUINA DE TURING

 Linguagens sensíveis ao contexto (Tipo 1 ):


Conjunto de linguagens aceitas por um autômato linearmente limitado, ou, de
forma equivalente, geradas pelas gramáticas sensíveis ao contexto



Todas as linguagens do Tipo 1 podem ser geradas através de gramáticas com
estrutura de frase (Tipo 0)



GRAMÁTICA SENSÍVEL AOCONTEXTO:

o Se às regras de substituição for imposta a restrição de que nenhuma
substituição possa reduzir o comprimento da forma sentencial à qual a
substituição é aplicada, cria -se uma classe de gramáticas ditas sensíveis
ao contexto
o Exemplo de gramática do Tipo 1 para a linguagem: L = { a nb2nan / n >= 1 }:

 Linguagens sensíveis ao contexto (Tipo 1 ):
G = ( {A, B, S}, {a, b}, P, S)



P={

S  aAbba | abba
aAb  aabbbB
Bb  b B
Ba  Caa | aa
bCa  Cba
b C  Cb
aCb  aAb }

AUTÔMATO LINEARMENTE LIMITADO:
o É uma Máquina de Turing (n ão determinística) que satisfaz as seguintes condições:

1. O alfabeto de entrada contém dois símbolos especiais * e $, usados como
marcadores do início e fim da fita
2. Não existem movimentos à esquerda de * nem à direita...
tracking img