Question

Pumping lemma

s. (7+5 points) Pumping lemma for regular languages. In all cases, -a,b) a) Consider the following regular language A. ping length p 2 1. For each string s e pumping lemma, we can write s -xy, with lyl S p, and s can be pumped. Since A is regular, A satisfies the pumping lemma with pum A, where Is] 2 p, by the a) Is p 3 a pumping length for language 4? (Yes/No) b) Show that w vhen the pumping length p -4, how the following strings can be pumped by dividing each string into three pieces, s- xyz, satisfying the three conditions. i)s -aaabb ii) s-aababb

Answer 1

a) A = aa (b union a)* ab* a) Here A can accept strings {aa, aab, aaab, ....}. Hence, yes, p = 3 is a pumping length for language A. b) i) s = aaabb [p = 4] x = aa, y = ab, z = b ii) s = aababb x = aa, y = b, z = abb.