# Is an irregular language concatenated with a language with which it has no common symbols irregular?

Here's an example of what I'm talking about. Suppose I have a languages
$$L_{1} = \{a^ib^i \mid i>0\},\\ L_{2} = \{c^i \mid i>0\}$$

and $$L_{1}L_{2} = \{a^ib^ic^i \mid i>0\}$$

Is it true that if $L_{1}$ is irregular and $L_{1}$ has no common symbols with $L_{2}$, then $L_{1}L_{2}$ is irregular? How would you prove this?

• Your $L_1 L_2$ should be $\{a^i b^i c^j \mid i > 0 \wedge j > 0\}$. – vonbrand Sep 17 '15 at 23:55

First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$ Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise $L1L2=\phi$ is clearly regular). This can be proved using Myhill–Nerode theorem.

Suppose $X$,$Y$ are any 2 different equivalence classes of $R_{L1}$, $x\in X, y\in Y$, then there exists string $z$ such that $xz \in L1$ while $yz \notin L1$.

If $L2=\{\epsilon\}$, then $L1L2$=$L1$ is irregular. Otherwise, take any string $w\in L2, w \neq \epsilon$, then $xzw \in L1L2$, but $yzw\notin L1L2$ (consider that, due to no common symbol, no suffix of $yzw$ longer than $|w|$ in L2, and no prefix of $yzw$ shorter than $|yz|$ in $L1$).

This shows that $x$,$y$ belongs to different equivalence classes of $R_{L1L2}$, too. ie. there must be at least the same number of equivalence classes in $R_{L1L2}$ as in $R_{L1}$

From Myhill–Nerode theorem, $L1$ has infinite number of equivalence classes. Thus $L1L2$ also has infinite number of equivalence classes, which means $L1L2$ is irregular also.

• if $L2=\emptyset$ then $L1L2=\emptyset$. Or did you mean something else by $\phi$? – Ran G. Sep 17 '15 at 19:17
• @RanG. corrected in answer. $L2=\phi$ is a special case that $L1L2=\phi$ is regular. – Terence Hang Sep 17 '15 at 23:26
• OK, that's what I thought. Better use \emptyset for $\emptyset$. – Ran G. Sep 17 '15 at 23:42

Yes: in general, if $L_1$ is a non-regular language over alphabet $\Sigma_1$, and $L_2$ is a language over some other alphabet $\Sigma_2$ with no symbols in common (i.e., $\Sigma_1 \cap \Sigma_2 = \emptyset$), and if $L_2$ is not the empty language ($L_2 \ne \emptyset$), then the language $L_1 L_2$ is also non-regular.

This follows from the closure properties of regular languages. In particular, if $L$ is a regular language and $f$ is a string homomorphism, then $f(L)$ (the homomorphic image of $L$ under $f$) is also regular. Now suppose $L_1 L_2$ was regular. Notice that

$$L_1 = f(L_1 L_2)$$

where $f$ is defined so that $f(x)=x$ for all $x \in \Sigma_1$ and $f(x)=\varepsilon$ for all $x \in \Sigma_2$. (This is a string homomorphism.)

So, by the closure property, if $L_1 L_2$ was regular, it would follow that $L_1$ was regular as well -- contradicting our assumption. The only possible conclusion is that if $L_1$ is not regular, then $L_1 L_2$ is not regular, either.

• if $\epsilon \notin L_2$, then $L_1L_2\cap \Sigma_1^*=\phi\neq L_1$ – Terence Hang Sep 15 '15 at 4:31
• @TerenceHang, thank you! I've corrected my answer; it should no longer have that issue. I should have used a string homomorphism from the start, rather than intersection. – D.W. Sep 15 '15 at 5:14

The nit-picking answer is actually NO, the language $L_1L_2$ is not necessarily nonregular. In order for the given proofs to work we have to require that $L_2\neq \varnothing$, since $L_1\varnothing = \varnothing$ which is regular.

The machinery given in the other answers (Myhill-Nerode and closure properties) is really useful and in general is preferable over ad hoc methods. Here however there is a very elegant (albeit ad hoc) construction. If we have a finite automaton for $L_1L_2$ and letters in the languages are disjoint, then we simply can replace all letters from $L_2$ by the empty string $\varepsilon$ and we get an automaton with $\varepsilon$-transitions for $L_1$. Assuming of course that $L_2\neq\varnothing$!

For this to work we only need to know that automata with $\varepsilon$-transitions are also defining regular languages.