# Automata and Computability

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 ad1c9bdddfhttps://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| ≤ 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