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


closed as unclear what you're asking by D.W., vonbrand, Juho, András Salamon, Luke Mathieson Mar 8 '14 at 6:42

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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

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.


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.


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.


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).

  • $\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.