Explore BrainMass
Share

Automata and Computability

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Consider the language B = L (G), where G is the grammar given in Exercise 2.13 (page 121). The pumping lemma for context-free languages, Theorem 2.19 (page 115), states the existence of a pumping length p for B. What is the minimum value of p that works in the pumping lemma? Justify your answer.

https://brainmass.com/computer-science/programming-languages/automata-computability-pumping-length-113142

Solution Preview

Solutiuon.
Recall that the minimum pumping length is the smallest positive integer l so that all words w of length at least l can be pumped with this pumping length, meaning that

w = uvxyz, |vy| > 0, |vxy| &#8804; l , uvixyiz ? L for i = 0, 1, ...

The procedure is to start trying to pump the shortest words until we seem able
to pump everything, and then make the general ...

Solution Summary

The expert examines automata and computability for pumping length.

\$2.19