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

3 Answers 3

1
$\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$
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$

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\} $

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – math boy
    Commented Dec 9, 2023 at 19:23
  • $\begingroup$ This here answer does not show that that language is a not a regular, let alone step by step. $\endgroup$
    – greybeard
    Commented Dec 10, 2023 at 15:06
  • 1
    $\begingroup$ following link contains answers to the question above. $\endgroup$
    – math boy
    Commented Dec 10, 2023 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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