Regular Languages and Concatenation

Question

Regular languages are closed under concatenation - this is demonstrable by having the accepting state(s) of one language with an epsilon transition to the start state of the next language.

If we consider the language L = {a^n | n >=0}, this language is regular (it is simply a*). If we concatenate it with another language L = {b^n | n >=0}, which is also regular, we end up with a^nb^n, but we obviously know this isn't regular.

Where am I going wrong with my logic here?

Answer 1

The definition of the concatenation of two languages L₁ and L₂ is the set of all strings wx where w ∈ L₁ and x ∈ L₂. This means that L₁L₂ consists of all possible strings formed by pairing one string from L₁ and one string from L₂, which isn't necessarily the same as pairing up matching strings from each language.

As a result, as @Oli Charlesworth pointed out, the language you get back here isn't actually { aⁿbⁿ | n in N }. Instead, it's the language { aⁿb^m | n in N and m in N }, which is the language a*b*. This language is regular, since it's given by the regular languages.

Hope this helps!