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 mecanismos generativos definidos pelas gramáticas corresponde exatamente ao conjunto das linguagens que esta classe de gramáticas é capaz de gerar. A esta classe de gramáticas, a hierarquia de Chomsky classifica como sendo a dasGramáticas com Estrutura de Frase ou Tipo 0. Chamam-se linguagens do tipo 0 todas as linguagens que podem ser geradas por alguma gramática do tipo 0. Para gramáticas do tipo 0, as produções são todas da forma a Þ b, a Î (Vn U Vt)+, b Î (Vn U Vt)*.

Exemplo: G = ({A, B, C}, {a, b}, P, A) P: A Þ BC BC Þ CB B Þ b C Þ a L(G) = {ba, ab} 2. Gramáticas Sensíveis ao Contexto ou Tipo 1 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. As gramáticas que obedecem a estas restrições pertencem, na hierarquia de Chomsky, ao conjunto das Gramáticas Sensíveis ao Contextoou do Tipo 1. Chamam-se linguagens do tipo 1 todas aquelas que podem ser geradas por alguma gramática do tipo 1. Note-se que todas as linguagens do tipo 1 podem ser geradas através de gramáticas com estrutura de frase ou

Relacionados

  • Hierarquia chomsky
    1550 palavras | 7 páginas
  • Trabalho Hierarquia De Chomsky
    967 palavras | 4 páginas
  • Hieraqruia
    613 palavras | 3 páginas
  • Compiladores
    1301 palavras | 6 páginas
  • 3 Trabalho De Teoria Da Computa O
    2174 palavras | 9 páginas
  • Sistemas de informação
    883 palavras | 4 páginas
  • hierarquia de chowsky
    848 palavras | 4 páginas
  • Ciencia da computacao
    575 palavras | 3 páginas
  • Lev Vygotsky e Chonsk
    8812 palavras | 36 páginas
  • Chomysk
    1612 palavras | 7 páginas