Problem Detail: 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?
$$ 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?
Asked By : ebracho
Answered By : Terence Hang
First, your $L1L2$ is wrong. $$L1L2 = {a^ib^ic^j | i>0, j>0}$$ Your conclusion is right, $L1L2$ is irregular(as long as $L2neqphi$, 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}$, $xin X, yin 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 $win L2, w neq epsilon$, then $xzw in L1L2$, but $yzwnotin 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47188
