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

Question

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

Answer 1

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.

Answer 2

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