# 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. Commented Oct 18, 2021 at 16:24
• Please see tips and suggestions in our reference question. Commented Oct 18, 2021 at 17:19
• Does this answer your question? How to prove that a language is not regular? Commented Aug 9, 2023 at 20:16

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.

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$$.

isn't this the same problem: https://stackoverflow.com/questions/2309752/why-is-anbn-n-0-not-regular

$$if \,\,\,\, |x|=|y| \,\,\,\, then \,\,\,\ L = \{a^n b^n \mid n \geq 0\}$$

• I don't understand why the answer got downvoted, I simply referenced to the question, which I think is the same. I would like to know, why question I linked not the same as the question asked here. Commented Dec 9, 2023 at 19:23
• This here answer does not show that that language is a not a regular, let alone step by step. Commented Dec 10, 2023 at 15:06
• following link contains answers to the question above. Commented Dec 10, 2023 at 19:36