Exemplo de uma linguagem livre de contexto que, no entanto, PODE ser bombeada?

Portanto, basicamente L satisfaz as condições do lema de bombeamento para CFLs, mas não é uma CFL (isso é possível de acordo com a definição do lema).

O exemplo clássico é . Wise mostra em seu artigo Um forte lema de bombeamento para linguagens sem contexto que nem o lema de Bar-Hillel nem o teorema de Parikh (afirmando que o conjunto de comprimentos de palavras em uma linguagem sem contexto é semi-linear) podem ser usados ​​para provar que L não é livre de contexto. Outros truques como cruzar com um idioma comum também não ajudam. (O lema de Ogden, uma generalização do lema de bombeamento de Bar-Hillel, prova que $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$$L$$L$Ele também fornece um lema de bombeamento alternativo equivalente à ausência de contexto (para linguagens computáveis) e o utiliza para provar que não é livre de contexto.$L$

O lema de bombeamento de Wise afirma que uma linguagem é livre de contexto se e somente se houver uma gramática (irrestrita) G gerando L e um número inteiro k, de modo que sempre que G gere uma "forma sentencial" s (para que s possam incluir não terminais) de comprimento | s | > k , podemos escrever s = u v x y z onde x , v y não estão vazios, | v x y | ≤ $L$$G$$L$$k$$G$$s$$s$$|s| > k$$s = uvxyz$$x,vy$$|vxy| \leq k$, E não é um produto não-terminal de tal forma que L gera u Um z e A gera tanto v Um y e x .$A$$G$$uAz$$A$$vAy$$x$

Ao aplicar repetidamente a condição no lema, o Wise pode provar que não é livre de contexto, mas os detalhes são um pouco complicados. Ele também fornece uma condição equivalente ainda mais complicada e a usa para provar que a linguagem { a n b a n m : n , m > 0 } não pode ser escrita como uma interseção finita de linguagens livres de contexto.$L$$\{ a^n b a^{nm} : n,m > 0 \}$

Se você não consegue acessar o artigo de Wise (está atrás de um paywall), há uma versão datilografada que saiu como um relatório técnico da universidade de Indiana.

---

Uma linguagem não isenta de contexto que satisfaça a condição de bombeamento do lema de Ogden é dada por Johnsonbaugh e Miller, Converse de lemas de bombeamento , e atribuída a Boasson e Horvath, em idiomas que satisfazem o lema de Ogden . O idioma em questão é Podemos escreverL′=L1∪

$$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$$ , correspondendo às duas linhas diferentes. Observe que L 1 ∩ L 2 = ∅ e que L 2 é regular. O lema de Ogden pode ser usado para provar que L 1 não é livre de contexto e, portanto, também não é L ' , mas não pode ser usadodiretamentepara mostrar que L ' não é livre de contexto.$L' = L_1 \cup L_2$$L_1 \cap L_2 = \emptyset$$L_2$$L_1$$L'$$L'$

Ainda mais simples: . Pode sempre bombear os a ; A interseção com o L regular ( a b + c + d + ) fornece um não-CFL (e isso pode ser provado pelo bombeamento do lema).$\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$$a$$\mathcal{L}(a b^+ c^+ d^+)$

A simple language is $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$. Intersect with $\mathcal{L}(a b^+ c^+ d^+)$ to get a clearly non-CFL, but you can always pump the $a$, and mimetize the equal-length-ness in the sea of ${}^+$.