Por que o lema Pumping para linguagens sem contexto usa o uvwxy, mas o uvw para os regulares?

Basicamente o que o título diz. Por que você pode "ignorar" a parte "xy" se deseja provar se um idioma é regular?

Ambos os lemas de bombeamento têm uma explicação intuitiva em termos de um autômato que pode reconhecer um idioma.

Uma linguagem regular pode ser reconhecida por um autômato finito. Todas as palavras são reconhecidas através de:

• um caminho finito através do autômato: palavras mais curtas que o comprimento do bombeamento;
• ou um caminho que passa por um nó no qual existe um loop; nesse caso, é possível percorrer o loop inúmeras vezes: esse é o $y^n$ parte, onde $y$ é o caminho através de uma rodada do loop e $n$ é o número de lops.

Uma linguagem livre de contexto pode ser reconhecida por um autômato de empilhamento. Todas as palavras são reconhecidas através de:

• um caminho finito através do autômato: palavras mais curtas que o comprimento do bombeamento;
• ou um caminho que inclua um loop com push para a pilha e outro loop com pops correspondentes. Empates e pops precisam se equilibrar para obter uma pilha vazia no final. Então a palavra contém um loop com push$v$, algum caminho adicional $w$e um loop com pops $x$. O número de execuções nos dois loops deve ser o mesmo, mas pode ser qualquer número, portanto, o bit do meio$v^n w x^n$.

Você também pode obter uma intuição semelhante das maneiras como as linguagens regulares e sem contexto podem ser especificadas por uma expressão regular e uma gramática sem contexto, respectivamente.

Se uma palavra é reconhecida por uma expressão regular, então:

• ou a palavra usa uma parte da expressão sob o $^*$ Operador (estrela Kleene), e essa parte $y$ pode ser repetido inúmeras vezes;
• ou a palavra não usa nenhuma parte da expressão sob uma estrela e não pode ser maior que a própria expressão.

Se uma palavra é reconhecida por uma gramática livre de contexto, então:

• Pode ser que a palavra seja reconhecida por uma árvore de análise onde existe uma subárvore $\mathcal{T}_1$ que é reconhecido pelo termo não-terminal $A$e uma subárvore $\mathcal{T}_0$ dessa subárvore é reconhecido pelo mesmo termo não-terminal $A$. Nesse caso, deixe$w$ seja a parte da palavra reconhecida por $\mathcal{T}_0$ e $vwx$ ser a parte que é reconhecida por $\mathcal{T}_1$. Você também obtém uma árvore de análise válida se substituir$\mathcal{T}_1$ de $\mathcal{T}_0$ou vice-versa. Além disso, desde$\mathcal{T}_1$ contém $\mathcal{T}_0$, depois de substituir $\mathcal{T}_0$ de $\mathcal{T}_1$, você pode substituir a cópia de $\mathcal{T}_0$ dentro $\mathcal{T}_1$ de $\mathcal{T}_1$, e assim por diante. Isso significa que você pode substituir$vwx$ de $w$, $v^2wx^2$, $v^3wx^3$, etc. e ainda recebe uma palavra com uma árvore de análise válida.
• Caso contrário, não há nenhuma subárvore da árvore de análise que reutilize o mesmo não-terminal e, nesse caso, o comprimento da palavra é limitado porque a profundidade da árvore de análise é limitada pelo número de não-terminais na gramática.

Isso é devido à "estrutura" das línguas que é observada pelos respectivos lemas de bombeamento. Veja as provas dos respectivos resultados de bombeamento.

Para linguagens regulares, a estrutura é linear e, para cada palavra longa, existe um estado que é repetido duas vezes no cálculo de aceitação de um autômato de estado finito. A string lida entre esses estados pode ser repetida.

A estrutura das linguagens sem contexto é aninhada, semelhante a uma árvore. Novamente, uma palavra longa terá uma árvore de derivação que repete um não-terminal em um dos caminhos da árvore. Essa estrutura também pode ser repetida, mas irá gerar duas cadeias, tanto para a esquerda quanto para a direita.

O lema de bombeamento para linguagens sem contexto é, no fundo, uma aplicação do princípio do buraco de pombo. Se pegarmos uma palavra longa o suficiente no idioma e considerarmos uma de suas árvores de análise, haverá um caminho no qual um dos não-terminais se repete. Isso nos permitirá "bombear" parte da palavra, por um processo de recortar e colar.

Como exemplo, considere a seguinte árvore de análise:

O não-terminal repetitivo é $A$. Podemos eliminar a repetição para obter a árvore de análise:

Também podemos "bombear" a repetição para obter a árvore de análise:

Em termos das próprias palavras, começamos com a palavra $sabacabas$, e obteve primeiro a palavra $sacas$ e então a palavra $sababacababas$.

O bombeamento corresponde à variação do número de aplicações da derivação $A \Rightarrow^* abAba$. Você pode ver que duas partes diferentes estão sendo bombeadas ao mesmo tempo. Isso é necessário para idiomas como$\{a^n b^n : n \geq 0\}$: a $a$ e $b$ as peças precisam ser bombeadas separadamente.

Considere agora o que acontece quando aplicamos os mesmos argumentos a uma gramática regular esquerda :

Como a gramática é deixada regular, a derivação bombeada $A \Rightarrow^* abA$contém apenas uma parte bombeada. Esse sempre será o caso das gramáticas regulares à esquerda, devido à forma das árvores de análise.

Em termos de decomposição $uvwxy$, isso implica que $x = \epsilon$, e entao $uv^iwx^iy = uv^iwy$, que é exatamente a forma do lema de bombeamento para idiomas regulares (considerando $wy$como uma única palavra). A forma particular das árvores de análise nas gramáticas regulares esquerdas nos permite obter um lema de bombeamento mais forte.

Crédito: todas as árvores de análise desenhadas usando o Syntax Tree Generator .