5
$\begingroup$

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?

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

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.

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

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.

$\endgroup$
  • $\begingroup$ if $\epsilon \notin L_2$, then $L_1L_2\cap \Sigma_1^*=\phi\neq L_1$ $\endgroup$ – Terence Hang Sep 15 '15 at 4:31
  • $\begingroup$ @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. $\endgroup$ – D.W. Sep 15 '15 at 5:14
5
$\begingroup$

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.

$\endgroup$

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.