# Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular language, I would appreciate if the answer could e given step by step, I really wnat to understand how it works .

Thank you :)

Show that $$\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$$ is a not a regular language

• This is the first example that textbooks usually give. Oct 18 '21 at 16:24
• Please see tips and suggestions in our reference question. Oct 18 '21 at 17:19

Let $$L$$ be your language. Suppose towards a contradiction that $$L$$ is regular and let $$p$$ be it's pumping length. Consider the word $$a^pb^p \in L$$. By the pumping lemma we can write it as $$a^i a^j b^p$$ with $$j \ge i$$ in such a way that, for all $$k \ge i$$, $$a^i a^{jk} b^p \in L$$. Pick $$k=0$$ to obtain $$a^i b^p \in L$$. This provides the sought contradiction since $$i < p$$.
Assume L is regular and is recognised by a state machine with N states. Then the strings $$a^k$$ for 0 ≤ k ≤ N cannot all end up in different states, because that would be N+1 different states. Therefore there are k ≠ k' such that $$a^k$$ and $$a^{k'}$$ end up in the same state.
If $$a^k$$ and $$a^{k'}$$ end up in the same state, then $$a^k w$$ and $$a^{k'} w$$ also end up in the same state, for every w. We pick $$w = b^k$$, and $$a^k b^k$$ and $$a^{k'} b^k$$ end up in the same state. However, the first is in the language and the second is not. Therefore the state would have to be both an accepting and a non accepting state, which is not possible. Therefore L is not regular.