Let's have this language:

$ L= \{ w_1 @ w_2 | w_1,w_2 \in \Sigma^*, \#_1(w_1)+(2*\#_2(w_1))=\#_1(w_2) + (2*\#_2(w_2)) \}$

$\Sigma = \{0,1,2\} \cup \{@\} $

I need to prove that this language is not regular by using pumping lemma. Where $\#_1(w_1) $ means count of symbols "1" in string $w_1$. I bet there is some easy solution with that symbol "@" in the middle of string, which we could possibly omit when pumping(maybe).


Just consider the string $111\cdots111 @ 111\cdots 111$, where the number of $1$'s is the same on both sides and is large: longer than the pumping length. Then the decomposition into $xyz$ must be such that $y$ contains only $1$'s, and so repeating it any number of times (other than exactly once) will make $\#_1(w_1) \neq \#_1(w_2)$.


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.