# Concatenation of regular languages [closed]

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

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

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