# pumping lemma, concatenation of non-regular languages $a \neq b$

Could use some help with the following question. I managed to prove using the pumping lemma that $$L_{a \neq b}$$, namely amount of a’s not equal to amount of b’s is not regular (using the lemma). But, I am having trouble showing whether the following language is regular or not (my intuition is that it is not regular) $$L_{a \neq b} \circ L_{a \neq b}$$.

• Perhaps surprisingly $L_{a\neq b} \cdot L_{a\neq b}$ is regular. It turns out that the strings not in $L_{a\neq b} \cdot L_{a\neq b}$ are of a very specific form. Commented Apr 22 at 15:50
• Oh… really? Can you please share how to prove it? Is there a DFA that easily accepts this language? Also how did you come to think of this Commented Apr 22 at 16:37
• Concatenation is such a strong operation, it is obvious that you can construct most things as concatenation of two strings with different numbers of a's and b's. How would you write aaabbb? How would you write aaabb? How would you write ababa or ababababa? The last two give you a stong hint. Commented Apr 24 at 22:16

Even if it seems strange, actually the language $$L=L_{a \neq b} \circ L_{a \neq b}$$ is regular, moreover, if $$\Sigma=\{a,b\}$$, then $$L$$ is "almost" $$\Sigma^+$$ (note that $$\epsilon \not\in L$$).

Indeed, let us try to understand which words belong to $$L$$. So, let $$w$$ be in $$\Sigma^*$$: we consider two main cases. If the lenght $$|w|$$ of $$w$$ is even (and greater than 0), than we can split $$w$$ into two words $$x$$ and $$y$$ of odd lenghts which surely belong to $$L_{a \neq b}$$, and then $$w=x\cdot y\in L$$.

So let $$|w|$$ be odd. It is easy to note that $$a$$ and $$b$$ do not belong to $$L$$, so suppose $$|w|\geq 3$$. Without loss of generality, let $$a$$ be the first letter of $$w$$, so $$w=a\cdot x$$, with $$x\in \Sigma^*$$ of even lenght and $$|x|\geq 2$$. If $$x\in L_{a \neq b}$$, then we have done, else, let $$c\in \Sigma$$ be the first letter of $$x$$, so that $$x=c\cdot y$$, with $$|y|\geq 1$$ of odd lenght. If $$c=a$$, then $$w=aa\cdot y$$ and $$aa, y\in L_{a \neq b}$$, and $$w\in L$$. So suppose $$c=b$$, i.e. $$w=ab\cdot y$$. Now $$ab\not\in L_{a \neq b}$$, so, in a sense, this prefix doesn't count in order to split $$w$$ in two words belonging to $$L_{a \neq b}$$. Therefore, we can apply the same resoning as above for $$w$$ to $$y$$. This way, we have constructed all the words not belonging to $$L$$ and starting with $$a$$: they are of the form $$ab\cdot y$$ with $$y$$ of odd lenght not belonging to $$L_{a \neq b}$$. This, with the base case $$w=a$$, implies that this kind of words forms the language $$M$$ satisfying the language equation $$M=abM+a$$, which has solution (see Arden's lemma) $$M=(ab)^*a$$.

The same reasoning applies for words starting with $$b$$, so $$L$$ is the complement of the language $$(ab)^*a+(ba)^*b+\epsilon$$, and then it is a regular language.

The reasoning above illustrates how to conjecture that $$L$$ is regular: the idea is to try to produce words that do not belong to $$L$$, and in general this is a good strategy in order to understand what it looks like a language (not necessarily regular). This leads to a recursive definition to which Arden's lemma is then applied.

However, now that we have a reasonable conjecture about the form of $$L$$, we can give a formal (and perhaps simpler) proof that $$L$$ is just the complement of $$(ab)^*a+(ba)^*b+\epsilon$$.

I will prove that (1) if $$w\in (ab)^*a+(ba)^*b+\epsilon$$, then $$w \not\in L$$, and that (2) if $$w\not \in (ab)^*a+(ba)^*b+\epsilon$$, then $$w \in L$$.

(1) Suppose $$w\in (ab)^*a+(ba)^*b$$ and let $$x$$ and $$y$$ be such that $$w=xy$$, then one of $$x$$ and $$y$$ has even length and cannot belong to $$L_{a \neq b}$$. Since this happens for every factorization of $$w$$ in $$xy$$, then $$w\not\in L$$.

(2) Conversely, suppose $$w$$ does not belong to $$(ab)^*a+(ba)^*b+\epsilon$$, we prove that $$w$$ belongs to $$L$$.

If $$|w|$$ is even, then as above we can write $$w=xy$$ with $$x$$ and $$y$$ of odd length, so $$x,y\in L_{a \neq b}$$ and thus $$w\in L$$.

So, suppose that $$|w|$$ is odd and does not belong to $$(ab)^*a+(ba)^*b$$. Then two consecutive equal letters must appear in $$w$$: without loss of generality suppose that $$w=x\cdot aa\cdot y$$ for some suitable $$x$$ and $$y$$. If $$x$$ is empty, then $$w=(aa)y$$ with $$aa,y\in L_{a \neq b}$$, so $$w\in L$$; if $$y$$ is empty, the same argument applies. So, in what follows I suppose $$x,y\neq \epsilon$$.

If $$x$$ is even and $$x\in L_{a \neq b}$$, then $$aay$$ has odd length and thus belongs to $$L_{a \neq b}$$, then $$w=x(aay)\in L$$. If $$x$$ is even and $$x\not \in L_{a \neq b}$$ (so $$x$$ has an equal number of $$a$$ and $$b$$), then $$x\cdot aa \in L_{a \neq b}$$, and thus the factorization $$w=(xaa)y$$ proves that $$w\in L$$. If $$x$$ has odd length, then $$y$$ has even length. In this case, if $$y\in L_{a \neq b}$$ then the factorization $$w=(xaa)y$$ still proves that $$w\in L$$, if, on the other hand, $$y\not\in L_{a \neq b}$$ then $$aay\in L_{a \neq b}$$ and thus the factorization $$w=x(aay)$$ proves that $$w\in L$$. This completes the proof.

• Thank you for the detailed proof. I haven’t thought of it like this. (Not trivial in my opinion) Commented Apr 23 at 10:38

The following is not a proof. It convinced me, but perhaps your professor does not accept proof-by-picture.

Draw stings over $$\{a,b\}$$ on the grid. For $$a$$ go up, for $$b$$ go down. Any string in $$L_{a\neq b}$$ -- for which the number of $$a$$'s and $$b$$'s does not match -- will end up on another level than where it started. Below $$aababbbaa$$ and $$ababa$$ are two examples. In both cases there, omitting the last $$a$$ will give a string outside $$L_{a\neq b}$$.

What about strings in $$L_{a\neq b} \cdot L_{a\neq b}$$? For those words we must be able to find a middle level which is different from both the first and last levels. We can do that most of the time. Except when the string has only two levels, and the first and last positions represent these levels. In that case all middle levels will match one of the exterior levels, meaning that half-string has the same number of $$a$$'s and $$b$$'s.

PS. Perhaps this idea does not look like a proof, but in fact only a little notation is needed to make it work. All our strings will be over $$\{a,b\}^*$$.

For a string $$w$$ the level of $$w$$ equals the integer $$\ell(w) = \#_a(w) - \#_b(w)$$. Clearly $$w\in L_{a\neq b}$$ if $$\ell(w) \neq 0$$. We will consider the levels of all the prefixes of a string.

We need an observation. Similar to the diagram, for a string $$uv$$, for the suffix we have $$v \in L_{a\neq b}$$ iff $$\ell(u) \neq \ell(uv)$$, or its begin and end-level are different. This follows from the fact that $$\ell(v) = \ell(uv) - \ell(u)$$ since clearly $$\ell(uv) = \ell(u) + \ell(v)$$.

By the above, a string can be written as $$uv$$ with both $$u, v\in L_{a\neq b}$$ iff $$\ell(u) \neq 0$$ and $$\ell(u) \neq \ell(uv)$$. In the diagram this means that we have found a position (prefix $$u$$) the level of which differs from the begin and end-levels of the string.

Thus a string $$w$$ does not belong to $$L_{a\neq b} \cdot L_{a\neq b}$$ iff every level (of a prefix) is either equal to the begin level (which is $$0$$) or equal to the end level ($$\ell(w)$$). That implies that the letters in the string should alternate (else we get at least three levels and we can find a middle position that differs from the begin and end levels) and that the final letter equals the last letter of the string (else $$\ell(w)=0$$ is unequal to the level of the first letter).

• Cool way to look at this. Thanks for sharing :) (indeed not a proof) Commented Apr 23 at 18:23