Question

Given a language b"a2nb" where n > 1. How many different ways are there to choose the substring y when applying the pumping lemma?

Answer 1

Given string is bⁿa²ⁿbⁿ where n > 1

The strings accepted by a language are L = { bbaaaabb , bbbaaaaaabbb , bbbbaaaaaaaabbbb , ....................................soo on}

we can pick any one of the strings to apply pumping lemma.

let us consider the string s = bbbaaaaaabbb

The substring y might changes based on the string choosen

Different automatas follow different rules for applying pumping lemma.

we can make this language possible by using context free language.

The rules are as follows to apply pumping lemma for context free language.

If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as

s = uvxyz ( our example: bbbaaaaaabbb )

with substrings u, v, x, y and z, such that

1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uvⁿxyⁿz is in L for all n ≥ 0.

There are number of chances to select y as a substring by following this rules.

NOTE:As mentioned above it is also dependent on the length of the string.