0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.