-2
$\begingroup$

Suppose we have two language

L = {0^n|n>=0}
M = {1^n|n>=0}

We know both of these are regular languages.

Will L.M (concatenation) be a regular language? Please explain your answer and if yes then what will be its expression?

Thanks for any help in advance.

Adding to it, we know that language {o^n1^n|n>=0} isn't a regular language

$\endgroup$
  • 1
    $\begingroup$ Simultaneous cross-post from cstheory. $\endgroup$ – Artem Kaznatcheev Mar 4 '14 at 2:46
  • $\begingroup$ @ArtemKaznatcheev - yes because I got reviews that this has more user percentage access. I am sorry for that. $\endgroup$ – Mcolorz Mar 4 '14 at 2:52
  • $\begingroup$ Hint. What does concatenation of two languages mean? So what strings are in $L.M$? So is that language regular? $\endgroup$ – David Richerby Mar 4 '14 at 8:38
  • $\begingroup$ @Mcolorz, for future reference, cross-posting violates site rules. Now you know. $\endgroup$ – D.W. Mar 5 '14 at 17:48
6
$\begingroup$

The two languages can be written in a slightly different way as :

  • $L = \{ 0^i | i\geq0\}$
  • $M = \{ 1^j | j\geq0\}$

When you concatenate, what you get is :

  • $L\circ M = \{ 0^i 1^j | i\geq0 , j\geq0\}$, which is, no doubt, a regular language.

What important thing you are overlooking is, you are adding the constraint $i=j$ mistakenly which takes it to the category of CFG.

$\endgroup$
4
$\begingroup$

Regular languages are precisely those languages that are recognized by some nfa. Therefore the concatenation $LM$ must be regular since their nfa recognizers can simply be concatenated (i.e. linking each accepting state of $L$'s nfa to the start state of $M$'s nfa with a $\epsilon$-transition).

This does not contradict $\{0^n1^n|n \geq 0 \}$ being context-free, since the variable $n$ in the definitions of $L$ and $M$ are bound and thus their instantiations are Independent from each other.

$\endgroup$
2
$\begingroup$

Just use the equivalence with regular expressions. Your first language is $0^*$ and the second is $1^*$. Their product is $0^*1^*$, which is also regular. More generally, the product of two regular languages is regular.

$\endgroup$
0
$\begingroup$

L1.L2 is regular, it represents a language having any number of 0's followed by any number of 1's. We can easily construct a DFA for this(Also RL's are closed under concatenation). But, L1.L2 is $\{0^n 1^m\mid m\ge 0, n\ge 0\}$. Here we have treat that two $n$'s differently (they are not related to each other).

$\endgroup$
  • $\begingroup$ What is meant by "I think its Gate 2014 CS Question."? Seems unrelated to the otherwise correct answer. $\endgroup$ – Patrick87 Mar 5 '14 at 23:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.