Search code examples
regular-languageautomatafinite-automatapumping-lemma

Use the pumping lemma to show that the following languages are not regular languages L = {anbm | n = 2m}

Use the pumping lemma to show that the following languages are not regular languages L = {an bm | n = 2m}

Solution

  • Choose a string a^2p b^p. The pumping lemma says we can write this as w = uvx such that |uv| <= p, |v| < 0 and for all natural numbers n, u(v^n)x is also a string in the language. Because |uv| <= p, the substring uv of w consists entirely of instances of the symbol a. Pumping up or down by choosing a value for n other than one guarantees that the number of a's in the resulting string will change, while the number of b's stays the same. Since the number of a's is twice the number of b's only when n = 1, this is a contradiction. Therefore, the language cannot be regular.