Concatenation of regular languages [closed]

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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