Hierarquia de Chomsky

903 palavras 4 páginas
Hierarquia de Chomsky

Em termos gerais, para n Î {0, 1, 2, 3} pode-se afirmar que uma gramática de qualquer tipo pode ser classificada também como sendo de tipo menor, se for o caso, de acordo com a Hierarquia de Chomsky. Analogamente, uma linguagem do tipo n é caracterizada pela existência de alguma gramática do tipo n que a descreva, podendo ser também classificada como sendo do tipo menor, se for o caso. GR = Gramáticas Regulares GLC = Gramáticas Livres de Contexto GSC = Gramáticas Sensíveis ao Contexto GEF = Gramáticas com Estrutura de Frase

1. Gramáticas com Estrutura de Frase ou Tipo 0 São aquelas às quais nenhuma limitação é imposta. Obviamente, todo o universo das linguagens que se pode definir através dos
…exibir mais conteúdo…
Gramáticas Livres de Contexto ou Tipo 2 Conceituam-se gramáticas livres de contexto como sendo aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções à forma geral
A Þ a onde A Î Vn, a Î (Vn U Vt)* . Segundo a hierarquia de Chomsky, esta classe de gramáticas é classificada como Livre de Contexto ou do Tipo 2. Denominam-se linguagens do tipo 2 aquelas que podem ser definidas através de gramáticas do tipo 2. Notar novamente a relação de inclusão: toda gramática ou linguagem do tipo 2 também é do tipo 1, e portanto do tipo 0. Outra maneira de se representar as Gramáticas Livres de Contexto é através da Forma Normal de Backus. As Linguagem Livres de Contexto também podem ser reconhecidas pelos Autômatos à Pilha.

Exemplo 1: G = ({S}, {a, +, *, (, )}, P, S) P = S Þ S * S S Þ S + S S Þ (S) S Þ a L(G) = conjunto das expressões aritméticas envolvendo *, +, ( ) e a. Um exemplo de cadeia formada por esta gramática é a * (a + a). Exemplo 2: G = ({S, A, B}, {a, b}, P, S) P : S Þ aB | bA A Þ a | aS | bAA B Þ b | bS | aBB L(G) = { x Î Vt+ | x contém número de a 's igual ao número de b 's } Exemplo 3: Processo inverso: dada L(G), determinar G. L(G) =

Relacionados

  • LINGUISTICA NA VISÃO DE CHOMSKY E SAUSSURE
    9544 palavras | 39 páginas
  • São Tomás de Aquino e a hierarquia dos seres
    1629 palavras | 7 páginas
  • Resenho Livro 11 de Setembro de Noam Chomsky
    1492 palavras | 6 páginas
  • Trabalho Hierarquia De Chomsky
    960 palavras | 4 páginas
  • Hierarquia das leis
    2782 palavras | 12 páginas
  • A hierarquia das necessidades de maslow e a teoria dos dois factores de herzberg
    1636 palavras | 7 páginas
  • Hierarquia e mobilidade social
    874 palavras | 4 páginas
  • Hierarquia de valores
    1770 palavras | 8 páginas