Hierarquia de Chomsky - Chomsky hierarchy

Na teoria da linguagem formal , ciência da computação e linguística , a hierarquia de Chomsky (ocasionalmente chamada de hierarquia de Chomsky-Schützenberger ) é uma hierarquia de contenção de classes de gramáticas formais .

Essa hierarquia de gramáticas foi descrita por Noam Chomsky em 1956. Ela também recebeu o nome de Marcel-Paul Schützenberger , que desempenhou um papel crucial no desenvolvimento da teoria das linguagens formais .

Gramáticas formais

Uma gramática formal deste tipo consiste em um conjunto finito de regras de produção ( lado esquerdo → lado direito ), onde cada lado consiste em uma sequência finita dos seguintes símbolos:

• um conjunto finito de símbolos não terminais (indicando que alguma regra de produção ainda pode ser aplicada)
• um conjunto finito de símbolos terminais (indicando que nenhuma regra de produção pode ser aplicada)
• um símbolo de início (um símbolo não terminal distinto)

Uma gramática formal fornece um esquema de axioma para (ou gera ) uma linguagem formal , que é um conjunto (geralmente infinito) de sequências de comprimento finito de símbolos que podem ser construídas aplicando regras de produção a outra sequência de símbolos (que inicialmente contém apenas o símbolo de início). Uma regra pode ser aplicada substituindo uma ocorrência dos símbolos em seu lado esquerdo por aqueles que aparecem em seu lado direito. Uma sequência de aplicações de regras é chamada de derivação . Tal gramática define a linguagem formal: todas as palavras consistindo apenas em símbolos terminais que podem ser alcançados por uma derivação do símbolo inicial.

Nonterminals muitas vezes são representados por letras maiúsculas, terminais por letras minúsculas, e o símbolo de início por S . Por exemplo, a gramática com terminais { a, b } , não terminais { S, A, B } , regras de produção

S → AB

S → ε (onde ε é a string vazia)

A → aS

B → b

e o símbolo inicial S , define o idioma de todas as palavras da forma (ou seja, n cópias de a seguidas de n cópias de b ). ${\ displaystyle a ^ {n} b ^ {n}}$

O que se segue é uma gramática mais simples que define a mesma linguagem:

Terminais { a, b } , não terminais { S } , símbolo de início S , regras de produção

S → aSb

S → ε

Como outro exemplo, uma gramática para um subconjunto de brinquedos do idioma inglês é dada por:

terminais

{gerar, odiar, ótimo, verde, ideias, linguistas}

não terminais

{ S, NP, VP, N, V, Adj }

regras de produção

S → NP VP

NP → Adj NP

NP → N

VP → V NP

VP → V

N → ideias

N → linguistas

V → gerar

V → odeio

Adj → ótimo

Adj → verde

e começar símbolo S . Um exemplo de derivação é

S → NP VP → Adj NP VP → Adj N VP → Adj NV NP → Adj NV Adj NP → Adj NV Adj NP → Adj NV Adj Adj N → ótimo NV Adj Adj N → ótimos lingüistas V Adj Adj N → ótimos lingüistas geram Adj Adj N → grandes linguistas geram ótimo Adj N → grandes linguistas geram ótimo verde N → grandes linguistas geram grandes ideias verdes.

Outras sequências que podem ser derivadas dessa gramática são: " ideias odeiam grandes linguistas " e " ideias geram ". Embora essas sentenças sejam absurdas, elas são sintaticamente corretas. Uma frase sintaticamente incorreta (por exemplo, " ideias, ideias, grande ódio ") não pode ser derivada desta gramática. Veja " Idéias verdes incolores dormem furiosamente " para um exemplo semelhante dado por Chomsky em 1957; consulte Gramática de estrutura de frase e Regras de estrutura de frase para exemplos de linguagem mais natural e os problemas de gramática formal nessa área.

A hierarquia

Conjunto de inclusões descritas pela hierarquia de Chomsky

A tabela a seguir resume cada um dos quatro tipos de gramáticas de Chomsky, a classe de linguagem que gera, o tipo de autômato que o reconhece e a forma que suas regras devem ter.

Gramática	línguas	Autômato	Regras de produção (restrições) *	Exemplos
Type-0	Recursivamente enumerável	Máquina de Turing	${\ displaystyle \ gamma \ rightarrow \ alpha}$ (sem restrições)	${\ displaystyle L = \ {w | w}$ descreve uma máquina de Turing terminada${\ displaystyle \}}$
Tipo 1	Sensível ao contexto	Máquina de Turing não determinística limitada linear	${\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$	${\ displaystyle L = \ {a ^ {n} b ^ {n} c ^ {n} | n> 0 \}}$
Tipo 2	Livre de contexto	Autômato pushdown não determinístico	${\ displaystyle A \ rightarrow \ alpha}$	${\ displaystyle L = \ {a ^ {n} b ^ {n} | n> 0 \}}$
Type-3	Regular	Autômato de estado finito	${\ displaystyle A \ rightarrow {\ text {a}}}$ e ${\ displaystyle A \ rightarrow {\ text {a}} B}$	${\ displaystyle L = \ {a ^ {n} | n \ geq 0 \}}$
* Significado dos símbolos: ${\ displaystyle {\ text {a}}}$ = terminal ${\ displaystyle A}$, = não terminal${\ displaystyle B}$ ${\ displaystyle \ alpha}$, , = Série de terminais e / ou não-terminais${\ displaystyle \ beta}$${\ displaystyle \ gamma}$ ${\ displaystyle \ alpha}$, = talvez vazio${\ displaystyle \ beta}$ ${\ displaystyle \ gamma}$ = nunca vazio

Observe que o conjunto de gramáticas correspondentes às linguagens recursivas não é membro dessa hierarquia; estes estariam corretamente entre o Tipo-0 e o Tipo-1.

Toda linguagem regular é livre de contexto, toda linguagem livre de contexto é sensível ao contexto, toda linguagem sensível ao contexto é recursiva e toda linguagem recursiva é recursivamente enumerável. Todas essas são inclusões adequadas, o que significa que existem linguagens recursivamente enumeráveis ​​que não são sensíveis ao contexto, linguagens sensíveis ao contexto que não são independentes do contexto e linguagens livres do contexto que não são regulares.

Gramáticas do tipo 0

As gramáticas do tipo 0 incluem todas as gramáticas formais. Eles geram exatamente todas as linguagens que podem ser reconhecidas por uma máquina de Turing . Essas linguagens também são conhecidas como linguagens recursivamente enumeráveis ou Turing-reconhecíveis . Observe que isso é diferente das linguagens recursivas , que podem ser decididas por uma máquina de Turing sempre parada .

Gramáticas tipo 1

Gramáticas do tipo 1 geram linguagens sensíveis ao contexto . Essas gramáticas têm regras da forma com um não-terminal e , e sequências de terminais e / ou não-terminais. As strings e podem estar vazias, mas não podem estar vazias. A regra é permitida se não aparecer no lado direito de nenhuma regra. As linguagens descritas por essas gramáticas são exatamente todas as linguagens que podem ser reconhecidas por um autômato linear limitado (uma máquina de Turing não determinística cuja fita é limitada por uma constante vezes o comprimento da entrada). ${\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$${\ displaystyle A}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ gamma}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle \ gamma}$${\ displaystyle S \ rightarrow \ epsilon}$${\ displaystyle S}$

Gramáticas tipo 2

As gramáticas do tipo 2 geram as linguagens livres de contexto . Eles são definidos por regras da forma como sendo um não terminal e uma sequência de terminais e / ou não terminais. Essas linguagens são exatamente todas as linguagens que podem ser reconhecidas por um autômato pushdown não determinístico . Linguagens livres de contexto - ou melhor, seu subconjunto de linguagem livre de contexto determinística - são a base teórica para a estrutura de frase da maioria das linguagens de programação , embora sua sintaxe também inclua resolução de nome sensível ao contexto devido a declarações e escopo . Freqüentemente, um subconjunto de gramáticas é usado para tornar a análise mais fácil, como por um analisador LL . ${\ displaystyle A \ rightarrow \ alpha}$${\ displaystyle A}$${\ displaystyle \ alpha}$

Gramáticas tipo-3

As gramáticas do tipo 3 geram as linguagens regulares . Tal gramática restringe suas regras a um único não terminal no lado esquerdo e um lado direito consistindo em um único terminal, possivelmente seguido por um único não terminal (regular direito). Alternativamente, o lado direito da gramática pode consistir em um único terminal, possivelmente precedido por um único não terminal (regular esquerdo). Eles geram os mesmos idiomas. No entanto, se as regras regulares à esquerda e as regras regulares à direita forem combinadas, a linguagem não precisa mais ser regular. A regra também é permitida aqui se não aparecer no lado direito de nenhuma regra. Essas linguagens são exatamente todas as linguagens que podem ser decididas por um autômato de estados finitos . Além disso, essa família de linguagens formais pode ser obtida por expressões regulares . Linguagens regulares são comumente usadas para definir padrões de pesquisa e a estrutura lexical das linguagens de programação. ${\ displaystyle S \ rightarrow \ varepsilon}$${\ displaystyle S}$

Referências

• Chomsky, Noam (1959). "Sobre certas propriedades formais das gramáticas" (PDF) . Informação e controle . 2 (2): 137–167. doi : 10.1016 / S0019-9958 (59) 90362-6 .
• Chomsky, Noam ; Schützenberger, Marcel P. (1963). “A teoria algébrica das linguagens livres de contexto”. Em Braffort, P .; Hirschberg, D. (eds.). Programação de computador e sistemas formais (PDF) . Amsterdã: Holanda do Norte. pp. 118–161.
• Davis, Martin D .; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidade, Complexidade e Linguagens: Fundamentos da Ciência da Computação Teórica (2ª ed.). Boston: Academic Press, Harcourt, Brace. p. 327 . ISBN 0-12-206382-1.