HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
concatenatedwithlanguagehasirregularwhichcommonsymbols

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#47188, answer score: 8

Revisions (0)

No revisions yet.