Gramática livre de contexto
A gramática livre de contexto (GLC), em teoria de linguagem formal, é uma gramática formal onde todas as regras de produções são da forma:
Desde o tempo de Pāṇini, pelo menos, os linguistas têm descrito as gramáticas de línguas em termos de sua estrutura de blocos, e descrito como as sentenças são recursivamente construídas a partir de frases menores e, eventualmente, palavras individuais ou elementos nominativos. Uma propriedade essencial destas estruturas de bloco é que as unidades lógicas não se sobrepõem. Por exemplo, a frase: Uma gramática livre de contexto fornece um mecanismo simples e matematicamente preciso para descrever os métodos pelos quais algumas frases em linguagem natural são construídas a partir de blocos menores, capturando a "estrutura de blocos" de frases de uma forma natural. Sua simplicidade faz o formalismo passível de rigoroso estudo matemático. Características importantes da sintaxe da linguagem natural, como acordo e referência, não fazem parte da gramática livre de contexto. Mas a estrutura recursiva básica de frases, a maneira em que cláusulas se alinham dentro de outras cláusulas, e a maneira em que lista de adjetivos e advérbios são engolidos por substantivos e verbos, são descritas precisamente.
A gramática livre de contexto é definida por uma 4-tuplas. G = ( V , Σ , R , S ) {\displaystyle G=(V,\Sigma ,R,S)} onde:
Notação das Regras de Produção
A regra de produção em R é formalizada matematicamente como um par ( α , β ) ∈ R {\displaystyle (\alpha ,\beta )\in R} , onde α ∈ V {\displaystyle \alpha \in V} é um não terminal e β ∈ ( V ∪ Σ ) ∗ {\displaystyle \beta \in (V\cup \Sigma )^{*}} é uma cadeia de variáveis e / ou terminais; ao invés de usar a notação par ordenado, regras de produção são geralmente escritos usando um operador seta com α como o seu lado esquerdo e β como o seu lado direito: α → β {\displaystyle \alpha \rightarrow \beta } . É permitido que β seja a cadeia vazia, e, neste caso, é habitual designar pelo ε. A forma α → ε {\displaystyle \alpha \rightarrow \varepsilon } é chamada de uma ε-produção.
Aplicação das Regras
Para quaisquer cadeias u , v ∈ ( V ∪ Σ ) ∗ {\displaystyle u,v\in (V\cup \Sigma )^{*}} , dizemos que u produz diretamente v, escrevendo como u ⇒ v {\displaystyle u\Rightarrow v\,} , se ∃ ( α , β ) ∈ R {\displaystyle \exists (\alpha ,\beta )\in R} sendo α ∈ V {\displaystyle \alpha \in V} and u 1 , u 2 ∈ ( V ∪ Σ ) ∗ {\displaystyle u_{1},u_{2}\in (V\cup \Sigma )^{*}} de forma que u = u 1 α u 2 {\displaystyle u\,=u_{1}\alpha u_{2}} e v = u 1 β u 2 {\displaystyle v\,=u_{1}\beta u_{2}} . Assim, v é o resultado da aplicação da regra ( α , β ) {\displaystyle (\alpha ,\beta )} para u.
Aplicacão repetida de regras
Para quaisquer palavra u , v ∈ ( V ∪ Σ ) ∗ , {\displaystyle u,v\in (V\cup \Sigma )^{*},} , dizemos u produz v, escrevendo como u ⇒ ∗ v {\displaystyle u{\stackrel {*}{\Rightarrow }}v} (ou u ⇒⇒ v {\displaystyle u\Rightarrow \Rightarrow v\,} como em alguns livros didáticos ), se ∃ k ≥ 1 ∃ u 1 , ⋯ , u k ∈ ( V ∪ Σ ) ∗ {\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma )^{*}} de forma que u = u 1 ⇒ u 2 ⇒ ⋯ ⇒ u k = v {\displaystyle u=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=v} . Neste caso, se k ≥ 2 {\displaystyle k\geq 2} (i.e., u ≠ v {\displaystyle u\neq v} ), a relação u ⇒ + v {\displaystyle u{\stackrel {+}{\Rightarrow }}v} mantém. Por outras palavras, ( ⇒ ∗ ) {\displaystyle ({\stackrel {*}{\Rightarrow }})} e ( ⇒ + ) {\displaystyle ({\stackrel {+}{\Rightarrow }})} são o fechamento transitivo reflexivo(permitindo uma palavra para produzir a si mesma) e o Fecho transitivo (que requer, pelo menos, uma etapa ) de ( ⇒ ) {\displaystyle (\Rightarrow )} , respectivamente.
Linguagem livre de contexto
A linguagem de uma gramática G = ( V , Σ , R , S ) {\displaystyle G=(V,\Sigma ,R,S)} é o conjunto Uma linguagem L é dito ser uma linguagem livre de contexto (CFL), se existe uma GLC L, de tal modo que L = L ( G ) {\displaystyle L\,=\,L(G)} .
GLC adequadas
Uma gramática livre de contexto é dita ser adequada, se tiver: Em teoria da linguagem formal, equivalência fraca de duas gramáticas significa que elas geram o mesmo conjunto de cadeias, ou seja, que a linguagem formal que eles geram é o mesmo. Cada gramática livre de contexto pode ser transformada em uma fracamente equivalente sem símbolos inacessíveis, uma fracamente equivalente sem símbolos improdutivos, e uma fracamente equivalente sem ciclos. Cada gramática livre de contexto que não possui produz ε pode ser transformada em uma fracamente equivalente sem ε-produções; Ao todo, cada tal gramática pode ser transformada em uma GLC adequada fracamente equivalente.
Exemplo
A gramática G = ( { S } , { a , b } , P , S ) {\displaystyle G=(\{S\},\{a,b\},P,S)} , com as produções: é livre de contexto. Não não é adequada uma vez que inclui um ε-produção. Uma derivação típica nesta gramática é Essa derivação deixa claro que L ( G ) = { w w R : w ∈ { a , b } ∗ } {\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}} . A linguagem é livre de contexto, no entanto, pode ser provado que não é regular.
A derivação de uma cadeia de caracteres para uma gramática é uma sequência de aplicações de regras de gramática que transforma o símbolo inicial na cadeia. Uma derivação prova que a sequência pertence à linguagem da gramática. A derivação é totalmente determinada fornecendo em cada passo: Para maior clareza, a cadeia intermediária geralmente é dada também. Muitas vezes, uma estratégia que é seguida deterministicamente determina o próximo não terminal que vai ser reescrito: Diante de tal estratégia, uma derivação é completamente determinada pela sequência de regras aplicadas. Por exemplo, a derivação mais à esquerda A distinção entre derivação mais à esquerda e mais à direita derivação é importante porque, na maioria dos parsers a transformação da entrada é definida por dar um pedaço de código para cada regra gramatical que é executado sempre que a regra é aplicada. Por isso, é importante saber se o parser determina o tipo de derivação mais a esquerda ou à direita, porque isso determina a ordem em que as partes de código vai ser executado. Veja por exemplo uma analisadores LL e analisadores LR.
Parênteses bem formados
O exemplo canônico de uma gramática livre de contexto é o da correspondência de parênteses, que é representante do caso geral. Há dois símbolos terminais "(" e ")" e um símbolo não terminal S. As regras de produção são A primeira regra permite que o símbolo S para multiplicar; a segunda regra permite que o símbolo S fique entre parênteses correspondentes; e a terceira regra termina a recursividade.
Parênteses aninhados e colchetes bem formados
Um segundo exemplo canônico é dois tipos diferentes de correspondência de parênteses aninhados, descritas pelas produções: Com os símbolos terminais [] () e o não terminal S. A sequencia a seguir pode ser derivads dessa gramática: No entanto, não há nenhuma gramática livre de contexto para a geração de todas as sequências de colchetes e parenteses, cada uma separadamente em relação desprezando as outras, mas onde os dois tipos não precisam alinhar um dentro da outra, por exemplo:
A Gramática Regular
Toda gramática regular é livre de contexto, mas nem todas as gramáticas livres de contexto são regulares. A gramática livre de contexto seguinte, no entanto, também é regular. Os terminais aqui são a e b, enquanto o único não terminal é S. A linguagem descrita é formada por todas as cadeias não vazias a {\displaystyle a} s e b {\displaystyle b} s que terminam em a {\displaystyle a} . Essa gramática é regular: nenhuma regra tem mais do que um não terminal em seu lado direito, e cada um desses não terminais é, ao mesmo ao fim do lado direito. Cada gramática regular corresponde diretamente a um autômato finito não determinístico, por isso sabemos que esta é uma linguagem regular.
Combinando pares
Em uma gramática livre de contexto, podemos emparelhar caracteres a forma como fazemos com os colchetes. O exemplo mais simples: Essa gramática gera a linguagem { a n b n : n ≥ 1 } {\displaystyle \{a^{n}b^{n}:n\geq 1\}} ,que não é regular ( de acordo com a regra dolema do bombeamento para linguagens regulares). O caractere especial ε serve para a cadeia vazia. Ao alterar a gramática acima para obtém-se uma gramática que gera a linguagem { a n b n : n ≥ 0 } {\displaystyle \{a^{n}b^{n}:n\geq 0\}} . Esta difere apenas por conter a cadeia vazia, enquanto a gramática original não tem.
Expressões Algébricas
Aqui está uma gramática livre de contexto para expressões algébricas sintaticamente corretas e infixas nas variáveis x, y e z: Essa gramática pode, por exemplo, gerar a cadeia Note-se que muitas opções foram feitas no andamento como a que foi reescrita vão ser realizadas em seguida. Estas escolhas parecem bastante arbitrárias. Por uma questão de fato, elas são, no sentido de que a cadeia gerada no final é sempre a mesma. Por exemplo, o segundo e terceiro reescritos Além disso, muitas escolhas foram feitas para que regra aplicar para cada S selecionado. Mudando as escolhas feitas e não apenas a ordem em que elas foram feitas, geralmente afetam qual terminal da cadeia vem no final.
Exemplos adicionais
Uma gramática livre de contexto para a linguagem consistindo de todas as cadeias sobre {a, b} contendo um número desigual de a's e b's: Aqui, o simbolo não terminal T pode gerar todas as cadeias com o mesmo número de a's e b's, o simbolo não terminal U gera todas as cadeias com mais a's do que de b's e o simbolo não terminal V gera todas as cadeias com menos a's do que b's. Omitindo a terceira alternativa na regra para U e V não restringe a linguagem da gramática. Outro exemplo de uma linguagem não regular é { b n a m b 2 n : n ≥ 0 , m ≥ 0 } {\displaystyle \{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 0\}} . É livre de contexto, uma vez que pode ser gerado pela seguinte gramática livre de contexto:
Toda gramática livre de contexto que não gera a cadeia vazia pode ser transformado em um em que não há ε-produção (isto é, uma regra que tem a cadeia vazia como um produto). Se uma gramática faz gerar a cadeia vazia, será necessário incluir a regra S → ϵ {\displaystyle S\rightarrow \epsilon } , mas não há necessidade de nenhuma outra regra ε. Toda gramática livre de contexto sem ε-produção tem uma gramática equivalente em forma normal de Chomsky ou forma normal de Greibach. "Equivalente", aqui, significa que as duas gramáticas gerar a mesma língua. A forma especialmente simples de regras de produção em gramáticas na Forma Normal de Chomsky tem implicações teóricas e práticas. Por exemplo, dada uma gramática livre de contexto pode-se usar a Forma Normal de Chomsky para construir um algoritmo de tempo polinomial que decide se uma determinada cadeia está na linguagem representado pela gramática ou não (o algoritmo CYK).
Linguagens livres de contexto são fechados sob união, concatenação, Fecho de Kleene, de Operações em cadeias de caracteres(em particular homomorfismo), homomorfismo inverso, e intersecção com uma linguagem regular. Elas não estão fechadas sob intersecção geral (por consequência não são fechadas no complemento) e diferença de conjunto.
Existem algoritmos para decidir se uma linguagem livre de contexto está vazio, e se ele é finito.
Algumas perguntas que são indecidíveis para as classes mais amplas de gramáticas se tornam decidíveis para gramáticas livres de contexto; por exemplo. o problema da vacuidade (se a gramática gera alguma cadeia de terminais), é indecidível para gramáticas sensíveis ao contexto, mas decidível para gramáticas livres de contexto. No entanto, muitos problemas são indecidíveis até mesmo para gramáticas livres de contexto. Alguns exemplos são:
Universalidade
Dada uma GLC, ela gera a linguagem de todas as cadeias sobre o alfabeto de símbolos terminais utilizados nas suas regras? Uma redução pode ser mostrada desse problema para o problema indecidível bem conhecido de se determinar se uma máquina de Turing aceita uma entrada particular (o Problema da parada). A redução utiliza o conceito de um histórico de computação, uma cadeia que descreve toda a computação de uma máquina de Turing. Uma GLC pode ser construída de forma que ela gera todas as cadeias que são histórias de computação de não aceitação para uma máquina de Turing particular sobre uma determinada entrada, e, portanto, ela irá aceitar todas as cadeias apenas se a máquina não aceita essa entrada.
Igualdade de linguagem
Dado duas GLCs, eles geram a mesma língua? A indecidibilidade do problema é uma consequência direta do anterior: é impossível até mesmo decidir se uma GLC é equivalente a GLC trivial que define a linguagem de todas as cadeias.
Inclusão de linguagem
Dadas duas GLCs, pode o primeiro gerar todas as cadeias que o segundo pode gerar? Se este problema foi decidível, em seguida, a igualdade de linguagem pode ser decidida também: dois GLCs G1 e G2 gerar a mesma língua se L(G1) é um subconjunto de L(G2) e L(G2) é um subconjunto de L(G1).
Estar em um nível inferior ou superior da hierarquia de Chomsky
Usando o teorema de Greibach, pode ser demonstrado que os dois seguintes problemas são indecidíveis:
Ambiguidade de gramática
A indecidibilidade deste problema resulta do fato de que, se existe um algoritmo para determinar a ambiguidade existente, o problema da correspondência de Post poderia ser decidido, que é conhecido como sendo indecidível.
Disjunção de linguagem
Dadas duas GLCs, existe alguma cadeia produzida a partir de ambas as gramáticas? Se o problema era decidível, o problema indecidível da Problema da correspondência de Post poderia ser decidido, para uma dada cadeia α 1 , … , α N , β 1 , … , β N {\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}} sobre algum alfabeto { a 1 , … , a k } {\displaystyle \{a_{1},\ldots ,a_{k}\}} , let the grammar G 1 {\displaystyle G_{1}} consist of the rule onde β i r e v {\displaystyle \beta _{i}^{rev}} denota a cadeia inversa β i {\displaystyle \beta _{i}} and b {\displaystyle b} não ocorre entre o a i {\displaystyle a_{i}} ; ;e deixe gramática G 2 {\displaystyle G_{2}} consistir da a regra
Uma maneira óbvia de estender o formalismo gramática livre de contexto é permitir não terminais de ter argumentos, cujos valores são repassados dentro das regras.Isso permite que recursos de linguagem naturais, tais como acordo e referência, e análogos de linguagens de programação, tais como o uso correto e definição de identificadores, para ser expressa de um modo natural. Por exemplo. agora podemos facilmente expressar que, em frases em inglês, o sujeito e o verbo deve concordar em número. Em ciência da computação, exemplos dessa abordagem incluem gramáticas de afixos, gramáticas de atributos, gramáticas indexada e Van Wijngaarden gramáticas de dois níveis. Extensões semelhantes existem em linguística. Uma gramática livre de contexto estendida (ou gramática parte direita regular) é aquele em que o lado direito das regras de produção é permitido ser uma expressão regular sobre os terminais e não terminais da gramática. Gramáticas livres de contexto estendida descrever exatamente linguagem livre de contexto.
Há um número de subclasses importantes das gramáticas livres de contexto: LR análise estende LL análise para apoiar uma maior gama de gramáticas; por sua vez, análise generalizada LR estende LR análise para apoiar gramáticas livres de contexto arbitrárias. Em gramáticas LL e gramáticas LR, elas essencialmente executam a LL análise e a LR análise, respectivamente, enquanto em gramáticas não determinísticas, é tão eficaz como pode ser esperado. Embora GLR análise foi desenvolvido na década de 1980 muitas novas definições de idioma e geradores de análise continuam a basear-se em LL, LR LALR ou analisar até os dias atuais.
Chomsky inicialmente esperou superar as limitações de gramáticas livres de contexto, adicionando regras de transformação. Tais regras são outro dispositivo padrão em linguísticas tradicionais; por exemplo forma passiva em inglês. Grande parte dagramática gerativa tem se dedicado a encontrar formas de aperfeiçoar os mecanismos descritivos da frase-estrutura gramatical e transformação de tal forma que governa exatamente os tipos de coisas que podem ser expressas em linguagem natural. Permitindo transformações arbitrárias não cumprem essa meta: elas são muito poderosas demais, sendo Turing completa a menos que restrições significativas são adicionados (por exemplo, não há transformações que introduzem e, em seguida, reescrever símbolos de uma forma livre de contexto). Posição geral de Chomsky sobre não-liberdade-de-contexto da linguagem natural tem se mantido desde então, embora seus exemplos específicos sobre a inadequação de gramáticas livres de contexto, em termos de sua capacidade geradora fraca foram mais tarde desmentida. Gerald Gazdar e Geoffrey Pullum argumentaram que, apesar de algumas construções não-livre de contexto em linguagem natural (tais como dependências cross-série em Suíço-alemão e reduplicação em Bambara), a grande maioria dos formulários em linguagem natural são, de facto livre de contexto.
