1
$\begingroup$

enter image description here

Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz.

The picture below is in support of the proof. enter image description here

I do not understand two things about this proof:

1) "we can assume that no variable repeats in the subtree T_5". Why should there not be any variable that repeats itself? Why is that a problem?

2) "Similarly, we can assume that no variable repeats in the subtrees T_3 and T_4." I don't quite see how we can fix the issue if there are variables that repeat in the subtrees T_3 or T_4?

$\endgroup$

1 Answer 1

1
$\begingroup$

It is certainly possible that some variables repeat in the subtree $T_3$, $T_4$ or $T_5$. There is nothing wrong with those situations, except that those situations are too relaxed for us to ensure "the lengths of the strings $v$, $x$, and $y$ depend only on the productions of the grammar and can be bounded independently of $w$ so that (8.2) holds"


Let us verify that we are able to assume those two assumptions.

One way to enable those two assumptions is described in the textbook. I will let you to convince yourself it works.

Here is a slightly different way to enable those two assumptions. We know that there are repeated variables on some path from the root to a leaf. Choose a pair of the same variable so that the number of nodes in the subtree rooted at the upper appearance of the variable is the smallest among all possible such pairs. Let that pair be shown as the two $A$s in the following derivation, which corresponds to figure 8.1.

$$ S\stackrel{*}{\implies}uAz\stackrel{*}{\implies}uvAyz\stackrel{*}{\implies}uvxyz$$

There is no repeated variable in subtrees $T_3$, $T_4$ and $T_5$, since any repeated variable in $T_3$, $T_4$ or $T_5$, say $B$, means the subtree rooted at the upper appearance of $B$ has smaller number of nodes than the subtree rooted at the upper $A$ (as the former tree is strictly contained in the latter tree), which contradicts to how $A$s in the figure have been selected.


That means any path from the upper $A$ to any leaf in the tree passes at most $|V|+2$ nodes, where $V$ is the set of variables. ("$+2$" since $A$ may appear twice in that path and the leaf node holds a terminal symbol instead a variable') Since each node can have at most $\ell$ children, where $\ell$ is the maximum length of the string on the right side of any production, the number of leaves in the subtree rooted at the upper $A$ is at most $\ell^{|V|+1}$, i.e., $|vxy|\le\ell^{|V|+1}$. Note $\ell^{|V|+1}$ is a constant that depends on the grammar only.

$\endgroup$
1
  • $\begingroup$ Thank you for this well-explained answer! Pretty much everything is clear to me now. The only thing I still don’t quite understand is why we are sure that “Because of the way A has been chosen, there is no repeated variable in subtrees T_3, T_4, and T_5”. I actually don’t fully understand what T_3 and T_4 represent. Could you perhaps add a little more explanation on this part with a small grammar-example on what T_3 and T_4 in that example would be? $\endgroup$ Jun 21 at 11:58

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.