Explore BrainMass
Share

# Automata and Computability

This content was STOLEN 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