Hierarquia de Chomsky

Na teoria da linguagem formal, ciência da computação e lingüística, a hierarquia de Chomsky é uma hierarquia de contenção de classes de gramáticas formais. Essa hierarquia de gramáticas foi descrita por Noam Chomsky em 1956.

Gramáticas formais

Uma gramática formal desse 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 símbolos de comprimento finito que podem ser construído aplicando regras de produção a outra sequência de símbolos (que inicialmente contém apenas o símbolo inicial). 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 que consistem apenas em símbolos terminais que podem ser alcançados por uma derivação do símbolo inicial.

Os não terminais geralmente são representados por letras maiúsculas, os terminais por letras minúsculas e o símbolo inicial 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 → ASS

B → b)

e símbolo de início S, define a linguagem de todas as palavras do formulário umnb)n{displaystyle a^{n}b^{n}} (i.e. n cópias de um seguido por n cópias de b)).

O seguinte é uma gramática mais simples que define o mesmo idioma:

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

S → A Sb

S → ε

Como outro exemplo, uma gramática para um subconjunto toy da língua inglesa é dada por:

terminais

(generado, ódio, grande, verde, ideias, linguistas)

não terminais

(S, NP, VP, N, V, Adj?

regras de produção

S → PN VP

PN → Adj PN

PN → N

VP → V PN

VP → V

N → ideias

N → linguistas

V → gerar

V → ódio

Adj → grande

Adj → verde verde

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

S → NP VP → Adj NP VP → Adj N VP → Adj N V NP → Adj N V Adj NP → Adj N V Adj Adj NP → Adj N V Adj Adj N → grande N V Adj Adj N → grandes linguistas V Adj Adj N → grandes linguistas geram Adj Adj N → grandes linguistas geram grande Adj N → grandes linguistas geram grande 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&# 34;. Embora essas frases sejam sem sentido, elas são sintaticamente corretas. Uma frase sintaticamente incorreta (por exemplo, "idéias, idéias, muito ódio") não pode ser derivada dessa gramática. Consulte "Idéias verdes incolores dormem furiosamente" para um exemplo semelhante dado por Chomsky em 1957; consulte Gramática de estrutura frasal e Regras de estrutura frasal para obter mais exemplos de linguagem natural e os problemas de gramática formal nessa área.

A hierarquia

Definir inclusões descritas pela hierarquia de Chomsky

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

Gramática	Línguas	Automóvel	Regras de produção (constrições)*	Exemplos
Tipo-0	Recursivamente enumerável	Máquina de Turing	γ γ → → α α {displaystyle gamma rightarrow alpha } (γ γ - Sim. não vazio)	L= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(O quê?|O quê?Não. L={w|w} descreve uma máquina de Turing terminante?{displaystyle }}
Tipo 1	Contexto sensível	Não-determinístico linear Máquina de Turing	α α Aβ β → → α α γ γ β β {displaystyle alpha Abeta rightarrow alpha gamma beta }	0}}" xmlns="http://www.w3.org/1998/Math/MathML">L= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umnb)ncn|n>0?Não. L={a^{n}b^{n}c^{n}|n>0}}0}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2bb63b71ffcba840f36e802aafe4c9951cf9ec38" style="vertical-align: -0.838ex; width:20.198ex; height:2.843ex;"/>
Tipo-2	Sem contexto	Autômatos de pushdown não determinísticos	A→ → α α Não. Arightarrow alpha }	0}}" xmlns="http://www.w3.org/1998/Math/MathML">L= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umnb)n|n>0?Não. L={a^{n}b^{n}|n>0}}0}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dfafe0fa14e5249f492f5cbde42062ba4904d56f" style="vertical-align: -0.838ex; width:17.973ex; height:2.843ex;"/>
Tipo 3	Regular	Autômato de estado finito	A→ → umNão. Arightarrow {text{a}}} e A→ → umBNão. Arightarrow {text{a}}B}	L= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umn|n≥ ≥ 0?{displaystyle L={a^{n}|ngeq 0}}
* Significado de símbolos: um{displaystyle {text{a}}} = terminal ANão. A., BNão. = não-terminal α α - Sim., β β - Sim., γ γ - Sim. = cadeia de terminais e/ou não terminais

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 apropriadas, 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 livres de contexto e linguagens livres de 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 do tipo 1

As gramáticas tipo 1 geram linguagens sensíveis ao contexto. Estas gramáticas têm regras da forma α α Aβ β → → α α γ γ β β {displaystyle alpha Abeta rightarrow alpha gamma beta } com ANão. A. um não-terminal e α α - Sim., β β - Sim. e γ γ - Sim. strings de terminais e/ou não terminais. As cordas α α - Sim. e β β - Sim. pode estar vazio, mas γ γ - Sim. Deve ser nada. A regra S→ → ε ε Não. Srightarrow epsilon } é permitido se SNão. S. não aparece no lado direito de qualquer regra. As linguagens descritas por estas gramáticas são exatamente todas as linguagens que podem ser reconhecidas por um autômato linear limitado (uma máquina de Turing nondeterminística cuja fita é limitada por um tempo constante o comprimento da entrada.)

Gramáticas do tipo 2

As gramáticas tipo-2 geram as linguagens livres de contexto. Estes são definidos por regras do formulário A→ → α α Não. Arightarrow alpha } com ANão. A. ser um não-terminal e α α - Sim. ser uma cadeia de terminais e/ou não terminais. Essas linguagens são exatamente todas as linguagens que podem ser reconhecidas por um autômato não determinístico. As 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 frases da maioria das linguagens de programação, embora sua sintaxe também inclui resolução de nome sensível ao contexto devido a declarações e escopo. Muitas vezes um subconjunto de gramáticas é usado para tornar a análise mais fácil, como por um parser LL.

Gramáticas do tipo 3

As gramáticas tipo 3 geram as linguagens regulares. Essa gramática restringe suas regras a um único não-terminal no lado esquerdo e um lado direito que consiste em um único terminal, possivelmente seguido por um único não-terminal (direita regular). Alternativamente, o lado direito da gramática pode consistir em um único terminal, possivelmente precedido por um único não-terminal (à esquerda regular). Estas geram as mesmas línguas. No entanto, se as regras esquerda-regulares e as regras direita-regulares forem combinadas, a linguagem não precisa mais ser regular. A regra S→ → ε ε Não. Srightarrow varepsilon } também é permitido aqui se SNão. S. não aparece no lado direito de qualquer regra. Estas linguagens são exatamente todas as linguagens que podem ser decididas por um autômato de estado finito. Além disso, esta família de línguas formais pode ser obtida por expressões regulares. As linguagens regulares são comumente usadas para definir padrões de pesquisa e a estrutura lexical das linguagens de programação.