7
$\begingroup$

Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?

$\endgroup$
13
$\begingroup$

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language.

A regular language can be recognized by a finite automaton. All words are recognized through:

  • either a finite path through the automaton: words that are shorter than the pumping length;
  • or a path that goes through a node at which there is a loop, in which case it is possible to go through the loop any number of times: that's the $y^n$ part, where $y$ is the path through one round of the loop and $n$ is the number of lops.

A context-free language can be recognized by a pushdown automaton. All words are recognized through:

  • either a finite path through the automaton: words that are shorter than the pumping length;
  • or a path that includes both a loop with pushes to the stack, and another loop with corresponding pops. Pushes and pops have to balance in order to get an empty stack at the end. Then the word contains a loop with pushes $v$, some further path $w$, and a loop with pops $x$. The number of runs through the two loops has to be the same, but it can be any number, hence the middle bit $v^n w x^n$.

You can also get a similar intuition from the ways regular and context-free languages can be specified by a regular expression and a context-free grammar respectively.

If a word is recognized by a regular expression, then:

  • either the word does use a part of the expression under the $^*$ (Kleene star) operator, and that part $y$ can be repeated any number of times;
  • or the word doesn't use any part of the expression under a star, and it can't be longer than the expression itself.

If a word is recognized by a context-free grammar, then:

  • It may be that the word is recognized by a parse tree where there is a subtree $\mathcal{T}_1$ which is recognized by the nonterminal $A$, and a subtree $\mathcal{T}_0$ of that subtree is recognized by the same nonterminal $A$. In that case, let $w$ be the part of the word that is recognized by $\mathcal{T}_0$ and $vwx$ be the part that is recognized by $\mathcal{T}_1$. You also get a valid parse tree if you replace $\mathcal{T}_1$ by $\mathcal{T}_0$ or vice versa. Furthermore, since $\mathcal{T}_1$ contains $\mathcal{T}_0$, after replacing $\mathcal{T}_0$ by $\mathcal{T}_1$, you can replace the copy of $\mathcal{T}_0$ inside $\mathcal{T}_1$ by $\mathcal{T}_1$, and so on. This means that you can replace $vwx$ by $w$, $v^2wx^2$, $v^3wx^3$, etc. and still get a word with a valid parse tree.
  • Otherwise, there is no subtree of the parse tree which reuses the same nonterminal, and in that case the length of the word is bounded because the depth of the parse tree is bounded by the number of nonterminals in the grammar.
$\endgroup$
  • $\begingroup$ Also fun fact... there are progressively more complicated grammars (e.g. tree-adjoining grammars) that recognize progressively more complex languages (in this case apparently ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n > 0\}}$). $\endgroup$ – Mehrdad Jun 24 '18 at 10:54
6
$\begingroup$

That is because of the "structure" of the languages that is observed by the respective pumping lemma's. Have a look at the proofs of the respective pumping results.

For regular languages the structure is linear, and for every long word there is a state that is repeated twice in the accepting computation of a finite state automaton. The string read between these states can be repeated.

The structure of context-free languages is nested, tree-like. Again a long word will have a derivation tree that repeats a nonterminal on one of the paths in the tree. This structure also can be repeated, but will generate two strings, both to the left and right.

$\endgroup$
4
$\begingroup$

The pumping lemma for context-free languages is, at heart, an application of the pigeonhole principle. If we take any long enough word in the language and consider one of its parse trees, there will be a path in which one of the nonterminals repeats. This will allow us to "pump" part of the word, by a cut and paste process.

As an example, consider the following parse tree:

Parse tree

The repeating nonterminal is $A$. We can eliminate the repetition to obtain the parse tree:

Parse tree

We can also "pump" the repetition to obtain the parse tree:

Parse tree

In terms of the words themselves, we started with the word $sabacabas$, and obtained first the word $sacas$ and then the word $sababacababas$.

Pumping corresponds to varying the number of applications of the derivation $A \Rightarrow^* abAba$. You can see that two different parts are being pumped at the same time. This is necessary for languages like $\{a^n b^n : n \geq 0\}$: the $a$ and $b$ parts need to be pumped separately.

Consider now what happens when we apply the same arguments to a left regular grammar:

Parse tree

Since the grammar is left regular, the pumped derivation $A \Rightarrow^* abA$ only contains one pumped part. This will always be the case for left regular grammars, due to the form of the parse trees.

In terms of the decomposition $uvwxy$, this implies that $x = \epsilon$, and so $uv^iwx^iy = uv^iwy$, which is exactly the form of the pumping lemma for regular languages (considering $wy$ as a single word). The particular shape of the parse trees in left regular grammars enables us to obtain a stronger pumping lemma.

Credit: all parse trees drawn using Syntax Tree Generator.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.