Let P, Q & R be three languages, if P & R are regular and if PQ = R, then –

Key idea: From P and R being regular and PQ = R, we cannot deduce that Q must be regular. Q may be regular or non-regular. Given: P is regular

R is regular

PQ = R (concatenation of P and Q)

Regular languages are closed under concatenation: if both P and Q are regular, then PQ is regular. However, the converse is not true: even if PQ is regular, Q itself need not be regular. Example where Q is regular: Let the alphabet be {a, b}. Take P = a* (regular) and Q = b* (regular). Then PQ = a*b*, which is regular.

Example where Q is not regular but PQ is still regular: Let the alphabet be {a, b}. Take P = Σ* (the set of all strings over {a, b}), which is regular.

Let Q = {a^n b^n