Linguagem sem contexto

Na teoria da linguagem formal, uma linguagem livre de contexto (CFL) é uma linguagem gerada por uma gramática livre de contexto (CFG).

Linguagens livres de contexto têm muitas aplicações em linguagens de programação, em particular, a maioria das expressões aritméticas são geradas por gramáticas livres de contexto.

Fundo

Gramática livre de contexto

Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto. As propriedades intrínsecas da linguagem podem ser distinguidas das propriedades extrínsecas de uma gramática específica comparando várias gramáticas que descrevem a linguagem.

Autômatos

O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas pelos autômatos pushdown, o que torna essas linguagens passíveis de análise. Além disso, para um determinado CFG, há uma maneira direta de produzir um autômato pushdown para a gramática (e, portanto, o idioma correspondente), embora ir para o outro lado (produzindo uma gramática a partir de um autômato) não seja tão direto.

Exemplos

Um exemplo de linguagem livre de contexto é L= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umnb)n:n≥ ≥ 1?Não. L={a^{n}b^{n}:ngeq 1}}, a linguagem de todas as cordas de comprimento uniforme não vazias, todas as primeiras metades das quais são um's, e todas as segundas metades das quais são b)'s. L é gerado pela gramática S→ → umSb)|umb)Não. Sto aSb~|~ab}. Esta língua não é regular. É aceito pelo autômato pushdown M= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =((q0,q1,qf?,(um,b)?,(um,zangão.?,δ δ ,q0,zangão.,(qf?)Não. M=({q_{0},q_{1},q_{f}},{a,b},{a,z},deltaq_{0},z,{q_{f}}) ? Onde? δ δ - Sim. é definido como segue:

δ δ (q0,um,zangão.)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(q0,umzangão.)δ δ (q0,um,um)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(q0,umum)δ δ (q0,b),um)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(q1,ε ε )δ δ (q1,b),um)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(q1,ε ε )δ δ (q1,ε ε ,zangão.)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(qf,ε ε )(q_{0},a,z)\delta (q_{0},a)&=(q_{0},a)&=(q_{0},a,a)&=(q_{0},aa)\delta (q_{0},b,a)&=(q_{1},varepsilon)\delta (q_{1}

CFLs inequívocos são um subconjunto adequado de todas as CFLs: existem CFLs inerentemente ambíguas. Um exemplo de uma CFL inerentemente ambígua é a união de 0}}" xmlns="http://www.w3.org/1998/Math/MathML">(umnb)mcmDn|n,m>0?{displaystyle {a^{n}b^{m}c^{m}d^{n}|n,m>0}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1689dcc0d3be90d07a80fbeeec438df392f1d68" style="vertical-align: -0.838ex; width:21.941ex; height:2.843ex;"/> com 0}}" xmlns="http://www.w3.org/1998/Math/MathML">(umnb)ncmDm|n,m>0?{displaystyle {a^{n}b^{n}c^{m}d^{m}|n,m>0}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/29037566431d767d77c51da15bb35767a7282208" style="vertical-align: -0.838ex; width:21.941ex; height:2.843ex;"/>. Este conjunto é livre de contexto, uma vez que a união de duas línguas sem contexto é sempre livre de contexto. Mas não há nenhuma maneira de analisar inequivocamente cordas no subconjunto (não-contexto-livre) 0}}" xmlns="http://www.w3.org/1998/Math/MathML">(umnb)ncnDn|n>0?{displaystyle {a^{n}b^{n}c^{n}d^{n}|n>0}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54821069981403337b3b368f9217da5514336d50" style="vertical-align: -0.838ex; width:17.954ex; height:2.843ex;"/> que é a interseção destas duas línguas.

Linguagem dick

A linguagem de todos os parênteses devidamente combinados é gerada pela gramática S→ → SS|(S)|ε ε Não. Sto SS~|~(S)~|~varepsilon }.

Propriedades

Análise sem contexto

A natureza livre de contexto da linguagem simplifica a análise com um autômato pushdown.

Determinar uma instância do problema de associação; ou seja, dada uma string O quê?Não., determinar se O quê?∈ ∈ L(G)(G)} Onde? LNão. L. é a linguagem gerada por uma dada gramática GNão. G.; é também conhecido como reconhecimento. O reconhecimento livre de contexto para as gramáticas da forma normal de Chomsky foi mostrado por Leslie G. Valiant para ser redutível para a multiplicação da matriz booleana, herdando assim sua complexidade superior vinculado de O(n^2.37285). Por outro lado, Lillian Lee mostrou O(n^{3 a 3.}) multiplicação da matriz booleana a ser redutível O(n^{3 a 3}) A análise do CFG, estabelecendo assim algum tipo de limite inferior para este último.

Usos práticos de linguagens livres de contexto requerem também a produção de uma árvore de derivação que exiba a estrutura que a gramática associa com a string dada. O processo de produção desta árvore é chamado de parsing. Os analisadores conhecidos têm uma complexidade de tempo que é cúbica no tamanho da string que é analisada.

Formalmente, o conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas pelos autômatos pushdown (PDA). Os algoritmos do analisador para linguagens livres de contexto incluem o algoritmo CYK e o Algoritmo de Earley.

Uma subclasse especial de linguagens livres de contexto são as linguagens livres de contexto determinísticas que são definidas como o conjunto de linguagens aceitas por um autômato pushdown determinístico e podem ser analisadas por um analisador LR(k).

Consulte também gramática de expressão de análise como uma abordagem alternativa para gramática e analisador.

Propriedades de fechamento

A classe de linguagens livres de contexto é fechada nas seguintes operações. Ou seja, se L e P são linguagens livres de contexto, as seguintes linguagens também são livres de contexto:

• a união LTelecomunicações Telecomunicações PNão. Lcup P} de L e P
• a inversão de L
• a concatenação L)) PNão. Lcdot P} de L e P
• a estrela de Kleene L∗ ∗ Não. L^{*}} de L
• a imagem φ φ (L)(L)} de L sob um homomorfismo φ φ - Sim.
• a imagem φ φ - Sim. - Sim. 1(L)(L)} de L sob um homomorfismo inverso φ φ - Sim. - Sim. 1{displaystyle varphi ^{-1}}
• a mudança circular de L (a língua (vu:uv∈ ∈ L?{displaystyle {vu:uvin L}})
• o fechamento do prefixo L (o conjunto de todos os prefixos de strings de L)
• o quociente L/R de L por um idioma regular R

Não fechamento sob interseção, complemento e diferença

As linguagens livres de contexto não são fechadas sob interseção. Isso pode ser visto tomando as línguas A= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umnb)ncm∣ ∣ m,n≥ ≥ 0?Não. A={a^{n}b^{n}c^{m}mid m,ngeq 0}} e B= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ummb)ncn∣ ∣ m,n≥ ≥ 0?Não. B={a^{m}b^{n}c^{n}mid m,ngeq 0}}, que são ambos livres de contexto. A sua interseção é A─ ─ B= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(umnb)ncn∣ ∣ n≥ ≥ 0?Não. Acap B={a^{n}b^{n}c^{n}mid ngeq 0}}, que pode ser demonstrado ser livre de contexto pelo lemma de bombeamento para línguas sem contexto. Como consequência, as línguas livres de contexto não podem ser fechadas em complemento, como para quaisquer línguas A e B, sua interseção pode ser expressa por união e complemento: A─ ─ B= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =A? ? Telecomunicações Telecomunicações B? ? ? ? Não. Acap B={overline {{overline {A}}cup {overline {B}}}}}}}}. Em particular, a linguagem livre de contexto não pode ser fechada sob a diferença, uma vez que o complemento pode ser expresso pela diferença: L? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Σ Σ ∗ ∗ ∖ ∖ L{displaystyle {overline {L}}=Sigma ^{*}setminus L..

No entanto, se L é uma linguagem sem contexto e D é uma linguagem regular, em seguida, ambas as interseções L─ ─ DNão. Lcap D} e sua diferença L∖ ∖ DNão. Lsetminus D} são línguas sem contexto.

Decidibilidade

Na teoria da linguagem formal, questões sobre linguagens regulares são geralmente decidíveis, mas questões sobre linguagens livres de contexto geralmente não são. É decidível se tal linguagem é finita, mas não se contém todas as strings possíveis, se é regular, não é ambígua ou se é equivalente a uma linguagem com uma gramática diferente.

Os seguintes problemas são indecidíveis para gramáticas livres de contexto A e B dadas arbitrariamente:

• Equivalência: é L(A)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =L(B)(A)=L(B)}?
• Disjuntamento: é L(A)─ ─ L(B)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =∅ ∅ {displaystyle L(A)cap L(B)=emptyset }? No entanto, a interseção de uma linguagem sem contexto e uma regular linguagem é livre de contexto, daí a variante do problema onde B é uma gramática regular é decidível (veja " vazio" abaixo).
• Contenção: é L(A)⊆ ⊆ L(B){displaystyle L(A)subseteq L(B)}? Novamente, a variante do problema onde B é uma gramática regular é decidível, enquanto que A é normal geralmente não.
• Universalidade: é L(A)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Σ Σ ∗ ∗ {displaystyle L(A)= Sigma ^{*}}?
• Regularidade: é L(A)(A)} uma língua normal?
• Ambiguidade: é cada gramática para L(A)(A)} ambígua?

Os seguintes problemas são Decidíveis para idiomas arbitrários sem contexto:

• Vazio: Dada uma gramática sem contexto A, L(A)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =∅ ∅ {displaystyle L(A)=emptyset }?
• Finiteness: Dada uma gramática livre de contexto A, L(A)(A)} finito?
• Membro: Dada uma gramática sem contexto Ge uma palavra O quê?Não., O quê?∈ ∈ L(G)(G)}? Algoritmos eficientes de tempo polinomial para o problema de associação são o algoritmo CYK e Algoritmo de Earley.

De acordo com Hopcroft, Motwani, Ullman (2003), Muitas das propriedades de fechamento fundamental e (não) de linguagens livres de contexto foram mostradas no artigo de 1961 de Bar-Hillel, Perles e Shamir

idiomas que não são livres de contexto

O conjunto 0}}" xmlns="http://www.w3.org/1998/Math/MathML">(umnb)ncnDn|n>0?{displaystyle {a^{n}b^{n}c^{n}d^{n}|n>0}}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54821069981403337b3b368f9217da5514336d50" style="vertical-align: -0.838ex; width:17.954ex; height:2.843ex;"/> é uma linguagem sensível ao contexto, mas não existe uma gramática livre de contexto gerando essa linguagem. Assim, existem linguagens sensíveis ao contexto que não são livres de contexto. Para provar que uma determinada língua não é livre de contexto, pode-se empregar o lemma de bombeamento para línguas sem contexto ou um número de outros métodos, como o lemma de Ogden ou o teorema de Parikh.