Question & Answer: Are there two non-regular languages whose concatenation is regular? Are there a countably infinite n…..

• The concatenation of two non regular languages can be regular , It can be proved as , Find the two non regular languages , for example L₀= {a^xb^y | x≠y } and L₁ = {b^qa^p | q≠p } ,

The concatenation of two languages can be wriiten as, L₀L₁ = { a^xb^y+qa^p | x≠y ∧ q≠p}

The concatenation can be proved by following conditions ,

when x=0,p=0 : y+q≥2

when x=0,p≠0 : y+q≥1

when x≠0,p=0: y+q≥1

when x=1,y+q≠1: p=1

Or else: y+q≥0

Hence the union of two regular languages is closed and concatenated L₀L₁ is regular.

• To prove that there are a countably infinite number of examples , Consider 5 set of languages P1 to P5 , It is obvious to say P1 to P5 are countably infinite , which can be proved by a set P for which exists , P={L|L=L₁∪L₂∪L₃∪L₄∪L₅,L₁∈P₁∧L₂∈P₂∧L₃∈P₃∧L₄∈P₄∧L₅∈P₅ } , The cross product of P₁ to P₅ is the cardinality set of P , and it is countably infinite set , Thus amount of such examples of countably infinite exists .
• Consider n and m be the set of P₁ to P₅ are numbers in natural numbers set , therefore it consists of infinite number of countably infinite sets , and the cross product of these countable sets is uncountably infinite , Hence uncountable infinite amount of such exmaples exists.