Question

Show that the language {aⁿbaᵐbaᵐⁿ:n,m≥1} is not regular.

Answer 1

To show that the language {aⁿbaᵐbaᵐⁿ:n,m≥1} is not regular, we can use the pumping lemma for regular languages and a counterexample.

Step-by-step explanation:

To show that the language {aⁿbaᵐbaᵐⁿ:n,m≥1} is not regular, we can use the pumping lemma for regular languages. Let's assume that the language is regular. According to the pumping lemma, there exists a constant p (the pumping length) such that any string s in the language with a length of at least p can be split into three parts, uvw, satisfying the following conditions:

1. The length of uv is less than or equal to p.
2. The length of v is greater than 0.
3. For all non-negative integers i, the string u(v^i)w is in the language.

Now, let's consider the string s = a^pba^pba^(2p). By the pumping lemma, we can split s into uvw such that |uv| ≤ p and |v| > 0. If we pump v, that is, repeat it any number of times (v^i), the number of 'a's before the first 'b' is not equal to the number of 'a's after the first 'b'. This means that u(v^i)w is no longer in the language, contradicting the pumping lemma. Therefore, the language {aⁿbaᵐbaᵐⁿ:n,m≥1} is not regular.