Explore BrainMass

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.

© BrainMass Inc. brainmass.com December 19, 2018, 11:13 pm ad1c9bdddf


Solution Preview

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| ≤ 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.