Gramática contextual - Context-sensitive grammar

A gramática sensível ao contexto ( CSG ) é uma gramática formal em que os lados da esquerda e lados direitos de quaisquer regras de produção pode ser rodeado por um contexto de terminais e símbolos não-terminais . Gramáticas sensíveis ao contexto são mais gerais do que gramáticas livres de contexto , no sentido de que existem linguagens que podem ser descritas por CSG, mas não por gramáticas livres de contexto. As gramáticas sensíveis ao contexto são menos gerais (no mesmo sentido) do que as gramáticas irrestritas . Assim, CSG são posicionados entre gramáticas livres de contexto e irrestritas na hierarquia de Chomsky .

Uma linguagem formal que pode ser descrita por uma gramática sensível ao contexto, ou, equivalentemente, por uma gramática não contratual ou um autômato linear limitado , é chamada de linguagem sensível ao contexto . Alguns livros didáticos realmente definem CSGs como não contratantes, embora não seja assim que Noam Chomsky os definiu em 1959. Esta escolha de definição não faz diferença em termos das línguas geradas (ou seja, as duas definições são fracamente equivalentes ), mas faz uma diferença em termos de quais gramáticas são consideradas estruturalmente sensíveis ao contexto; a última questão foi analisada por Chomsky em 1963.

Chomsky introduziu gramáticas sensíveis ao contexto como uma forma de descrever a sintaxe da linguagem natural, onde muitas vezes uma palavra pode ou não ser apropriada em um determinado lugar, dependendo do contexto. Walter Savitch criticou a terminologia "sensível ao contexto" como enganosa e propôs "não apagamento" como uma explicação melhor da distinção entre um CSG e uma gramática irrestrita .

Embora seja bem conhecido que certas características das linguagens (por exemplo , dependência serial cruzada ) não são livres de contexto, é uma questão em aberto quanto do poder expressivo do CSG é necessário para capturar a sensibilidade ao contexto encontrada em linguagens naturais. Pesquisas subsequentes nesta área se concentraram nas linguagens mais sensíveis ao contexto, mais tratáveis ​​computacionalmente . As sintaxes de algumas linguagens de programação visual podem ser descritas por gramáticas de gráfico sensíveis ao contexto .

Definição formal

Uma gramática formal G = ( N , Σ, P , S ), com N um conjunto de símbolos não terminais, Σ um conjunto de símbolos terminais, P um conjunto de regras de produção e S o símbolo inicial , é sensível ao contexto se todas as regras em P são da forma

α A β → αγβ

com A ∈ N , α, β ∈ ( N ∪Σ) ^* e γ ∈ ( N ∪Σ) ⁺ .

Uma string u ∈ ( N ∪Σ) ^* produz diretamente , ou deriva diretamente , uma string v ∈ ( N ∪Σ) ^* , denotada como u ⇒ v , se u pode ser escrito como l α A β r , ev pode ser escrito como l αγβ r , para alguma regra de produção (α A β → αγβ) ∈ P , e algumas strings de contexto l , r ∈ ( N ∪Σ) ^* . De forma mais geral, diz-se que u produz , ou deriva , v , denotado como u ⇒ ^* v , se u = u ₁ ⇒ ... ⇒ u _n = v para algum n ≥0 e algumas cadeias u ₂ , ... , u _{n -1} ( N ∪Σ) ^* . Ou seja, a relação (⇒ ^* ) é o fechamento transitivo reflexivo da relação (⇒).

A linguagem da gramática G é o conjunto de todas as cadeias de símbolos terminais deriváveis ​​de seu símbolo inicial, formalmente: L ( G ) = { w ∈ Σ ^* : S ⇒ ^* w }. Derivações que não terminam em uma string composta de símbolos terminais são possíveis, mas não contribuem para L ( G ).

A única diferença entre esta definição de Chomsky e aquela de gramáticas irrestritas é que γ pode ser vazio no caso irrestrito.

Algumas definições de uma gramática sensível ao contexto requerem apenas que para qualquer regra de produção da forma u → v, o comprimento de u deve ser menor ou igual ao comprimento de v. Este requisito aparentemente mais fraco é na verdade fracamente equivalente , consulte Não contratação gramática # Transformando-se em gramática sensível ao contexto .

Além disso, uma regra do formulário

S → λ

onde λ representa a string vazia e S não aparece no lado direito de nenhuma regra é permitido. A adição da string vazia permite a declaração de que as linguagens sensíveis ao contexto são um superconjunto adequado das linguagens livres de contexto, ao invés de ter que fazer a declaração mais fraca de que todas as gramáticas livres de contexto sem produções → λ também são gramáticas sensíveis ao contexto.

O nome sensível ao contexto é explicado pelos α e β que formam o contexto de A e determinam se A pode ser substituído por γ ou não. Isso é diferente de uma gramática livre de contexto em que o contexto de um não terminal não é levado em consideração. De fato, toda produção de uma gramática livre de contexto é da forma V → w, onde V é um único símbolo não-terminal ew é uma sequência de terminais e / ou não-terminais; w pode estar vazio.

Se a possibilidade de adicionar a string vazia a uma linguagem for adicionada às strings reconhecidas pelas gramáticas não contratantes (que nunca podem incluir a string vazia), então os idiomas nessas duas definições são idênticos.

As gramáticas sensíveis ao contexto à esquerda e à direita são definidas restringindo as regras apenas à forma α A → αγ e apenas A β → γβ, respectivamente. As linguagens geradas por essas gramáticas também são a classe completa de linguagens sensíveis ao contexto. A equivalência foi estabelecida pela forma normal de Penttonen .

Exemplos

A seguinte gramática sensível ao contexto, com o símbolo inicial S , gera a linguagem canônica não livre de contexto { a ⁿ b ⁿ c ⁿ  : n ≥ 1}:

1		S	→	uma	B	C
2		S	→	uma	S	B	C
3	C	B	→	C	Z
4	C	Z	→	C	Z
5	C	Z	→	C	C
6	C	C	→	B	C
7	uma	B	→	uma	b
8	b	B	→	b	b
9	b	C	→	b	c
10	c	C	→	c	c

As regras 1 e 2 permitem expandir S para a ⁿ BC ( BC ) ^{n -1} ; as regras 3 a 6 permitem a troca sucessiva de cada CB por BC ( quatro regras são necessárias para isso, uma vez que uma regra CB → BC não se encaixaria no esquema α A β → αγβ); as regras 7–10 permitem a substituição de um não-terminal B e C por seus terminais b e c correspondentes, respectivamente, desde que esteja no lugar certo. Uma cadeia de geração para aaabbbccc é:

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb bc CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

Gramáticas mais complicadas podem ser usadas para analisar { a ⁿ b ⁿ c ⁿ d ⁿ : n ≥ 1} e outras linguagens com ainda mais letras. Aqui nós mostramos uma abordagem mais simples usando gramáticas não contratantes: Iniciar com um kernel de produções regulares gerando as formas sentenciais e, em seguida, incluem as produções não contratantes , , , , , , , , , . ${\ displaystyle CSG}$${\ displaystyle (ABCD) ^ {n} abcd}$${\ displaystyle p_ {Da}: Da \ rightarrow aD}$${\ displaystyle p_ {Db}: Db \ rightarrow bD}$${\ displaystyle p_ {Dc}: Dc \ rightarrow cD}$${\ displaystyle p_ {Dd}: Dd \ rightarrow dd}$${\ displaystyle p_ {Ca}: Ca \ rightarrow aC}$${\ displaystyle p_ {Cb}: Cb \ rightarrow bC}$${\ displaystyle p_ {Cc}: Cc \ rightarrow cc}$${\ displaystyle p_ {Ba}: Ba \ rightarrow aB}$${\ displaystyle p_ {Bb}: Bb \ rightarrow bb}$${\ displaystyle p_ {Aa}: Aa \ rightarrow aa}$

Uma gramática não contratante (para o qual existe uma equivalente ) para a língua é definida por e , , , , , , . ${\ displaystyle CSG}$${\ displaystyle L_ {Cross} = \ {a ^ {m} b ^ {n} c ^ {m} d ^ {n}: m \ geq 1, n \ geq 1 \}}$${\ displaystyle p_ {1}: R \ rightarrow aRC | aC}$${\ displaystyle p_ {3}: T \ rightarrow BTd | Bd}$${\ displaystyle p_ {5}: CB \ rightarrow BC}$${\ displaystyle p_ {0}: S \ rightarrow RT}$${\ displaystyle p_ {6}: aB \ rightarrow ab}$${\ displaystyle p_ {7}: bB \ rightarrow bb}$${\ displaystyle p_ {8}: Cd \ rightarrow cd}$${\ displaystyle p_ {9}: Cc \ rightarrow cc}$

Com estas definições, uma derivação para é: . ${\ displaystyle a ^ {3} b ^ {2} c ^ {3} d ^ {2}}$${\ displaystyle S \ Rightarrow _ {p_ {0}} RT \ Rightarrow _ {p_ {1} ^ {2} p_ {2}} a ^ {3} C ^ {3} T \ Rightarrow _ {p_ {3} p_ {4}} a ^ {3} C ^ {3} B ^ {2} d ^ {2} \ Rightarrow _ {p_ {5} ^ {6}} a ^ {3} B ^ {2} C ^ {3} d ^ {2} \ Rightarrow _ {p_ {6} p_ {7}} a ^ {3} b ^ {2} C ^ {3} d ^ {2} \ Rightarrow _ {p_ {8} p_ {9} ^ {2}} a ^ {3} b ^ {2} c ^ {3} d ^ {2}}$

Uma gramática de não contratação para a linguagem { a ^{2 i}  : i ≥ 1} é construída no Exemplo 9.5 (p. 224) de (Hopcroft, Ullman, 1979):

1. ${\ displaystyle S \ rightarrow [ACaB]}$
2. ${\ displaystyle {\ begin {cases} \ [Ca] a \ rightarrow aa [Ca] \\\ [Ca] [aB] \ rightarrow aa [CaB] \\\ [ACa] a \ rightarrow [Aa] a [Ca ] \\\ [ACa] [aB] \ rightarrow [Aa] a [CaB] \\\ [ACaB] \ rightarrow [Aa] [aCB] \\\ [CaB] \ rightarrow a [aCB] \ end {cases} }}$
3. ${\ displaystyle [aCB] \ rightarrow [aDB]}$
4. ${\ displaystyle [aCB] \ rightarrow [aE]}$
5. ${\ displaystyle {\ begin {cases} \ a [Da] \ rightarrow [Da] a \\\ [aDB] \ rightarrow [DaB] \\\ [Aa] [Da] \ rightarrow [ADa] a \\\ a [DaB] \ rightarrow [Da] [aB] \\\ [Aa] [DaB] \ rightarrow [ADa] [aB] \ end {cases}}}$
6. ${\ displaystyle [ADa] \ rightarrow [ACa]}$
7. ${\ displaystyle {\ begin {cases} \ a [Ea] \ rightarrow [Ea] a \\\ [aE] \ rightarrow [Ea] \\\ [Aa] [Ea] \ rightarrow [AEa] a \ end {cases }}}$
8. ${\ displaystyle [AEa] \ rightarrow a}$

Forma normal de kuroda

Cada gramática sensível ao contexto que não gera a string vazia pode ser transformada em uma equivalente fracamente na forma normal de Kuroda . "Equivalente fraco" aqui significa que as duas gramáticas geram a mesma linguagem. A forma normal em geral não será sensível ao contexto, mas será uma gramática sem contratação .

A forma normal Kuroda é uma forma normal real para gramáticas não-contrativas.

Propriedades e usos

Equivalência ao autômato linear limitado

Uma linguagem formal pode ser descrita por uma gramática sensível ao contexto se e somente se for aceita por algum autômato linear limitado (LBA). Em alguns livros, esse resultado é atribuído apenas a Landweber e Kuroda . Outros o chamam de teorema Myhill –Landweber – Kuroda. (Myhill introduziu o conceito de LBA determinístico em 1960. Peter S. Landweber publicou em 1963 que a linguagem aceita por um LBA determinístico é sensível ao contexto. Kuroda introduziu a noção de LBA não determinístico e a equivalência entre LBA e CSGs em 1964.)

Em 2010, ainda é uma questão em aberto se todas as linguagens sensíveis ao contexto podem ser aceitas por um LBA determinístico .

Propriedades de fechamento

Linguagens sensíveis ao contexto são fechadas em complemento . Este resultado de 1988 é conhecido como teorema de Immerman – Szelepcsényi . Além disso, eles são fechados em união , interseção , concatenação , substituição , homomorfismo inverso e Kleene plus .

Toda linguagem recursivamente enumerável L pode ser escrita como h ( L ) para alguma linguagem sensível ao contexto L e algum homomorfismo de string h .

Problemas computacionais

O problema de decisão que pergunta se uma determinada string s pertence ao idioma de uma dada gramática G sensível ao contexto é PSPACE completo . Além disso, existem gramáticas sensíveis ao contexto cujas linguagens são PSPACE-completas. Em outras palavras, existe uma gramática sensível ao contexto G tal que decidir se uma certa string s pertence à linguagem de G é PSPACE completo (então G é fixo e apenas s faz parte da entrada do problema).

O problema do vazio para gramáticas sensíveis ao contexto (dada uma gramática G sensível ao contexto , é L ( G ) = ∅?) É indecidível .

Como modelo de linguagens naturais

Savitch provou o seguinte resultado teórico, no qual ele baseia sua crítica dos CSGs como base para a linguagem natural: para qualquer conjunto R recursivamente enumerável , existe uma linguagem / gramática G sensível ao contexto que pode ser usada como uma espécie de proxy para testar adesão em R na seguinte maneira: uma dada cadeia de s , s é em R , se e apenas se existe um número inteiro positivo n para os quais sc ⁿ é em L, onde C é um símbolo arbitrário que não faz parte de R .

Foi demonstrado que quase todas as línguas naturais podem, em geral, ser caracterizadas por gramáticas sensíveis ao contexto, mas toda a classe de CSGs parece ser muito maior do que as línguas naturais. Pior ainda, uma vez que o problema de decisão mencionado acima para CSGs é PSPACE-completo, isso os torna totalmente impraticáveis ​​para uso prático, já que um algoritmo de tempo polinomial para um problema PSPACE-completo implicaria P = NP .

Foi provado que algumas linguagens naturais não são livres de contexto, com base na identificação das chamadas dependências seriais cruzadas e fenômenos de embaralhamento ilimitado . No entanto, isso não implica necessariamente que toda a classe CSG seja necessária para capturar "sensibilidade ao contexto" no sentido coloquial desses termos em línguas naturais. Por exemplo, os sistemas de reescrita linear livre de contexto estritamente mais fracos (do que o CSG) (LCFRS) podem ser responsáveis ​​pelo fenômeno de dependências de série cruzada; pode-se escrever uma gramática LCFRS para { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1} por exemplo.

Investigação em curso sobre lingüística computacional tem-se centrado na formulação de outras classes de línguas que são " moderadamente sensível ao contexto " cujos problemas de decisão são viáveis, como gramáticas-contíguo de árvores , gramática categorial combinatória , linguagens livres de contexto acopladas e reescrita livre de contexto linear sistemas . As linguagens geradas por esses formalismos estão apropriadamente entre as linguagens livres de contexto e as sensíveis ao contexto.

Mais recentemente, a classe PTIME foi identificada com gramáticas de concatenação de intervalo , que agora são consideradas as mais expressivas das linguagens sensíveis ao contexto moderado.

Veja também

• Hierarquia de Chomsky
• Crescimento da gramática sensível ao contexto
• Gramática de cláusula definida # Gramáticas não livres de contexto
• Lista de geradores de analisador para gramáticas sensíveis ao contexto

Notas

Referências

Leitura adicional

• Meduna, Alexander ; Švec, Martin (2005). Gramáticas com condições de contexto e suas aplicações . John Wiley & Sons. ISBN 978-0-471-73655-4.

links externos

• Earley Parsing para Gramáticas Sensíveis ao Contexto