Question

Which of the following are regular sets?

I. {aⁿb²ᵐ | n≥0, m≥0}
II. {aⁿbᵐ | n=2m}
III. {aⁿbᵐ | n≠m}
IV. {xcy | x,y ∈ {a,b}*}

Accepted Answer

The correct answer is (A) I and IV only. I: n and m are independent (b^(2m) is just 'an even number of b's'), so this is a*(bb)* — regular. II requires n to be EXACTLY twice m, a counting/proportional relationship — provably non-regular (like aⁿbⁿ). III: if {aⁿbᵐ|n≠m} were regular, then a*b* minus it would give {aⁿbᵐ|n=m} regular too (closure under intersection with a regular set) — contradicting the well-known non-regularity of n=m, so III is non-regular. IV is simply {a,b}*·c·{a,b}* — a concatenation of regular languages, hence regular. So I and IV are regular.

Explanation