Explore BrainMass

Explore BrainMass

    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.

    © BrainMass Inc. brainmass.com October 9, 2019, 7:16 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.