1

Use the closure properties of regular languages and a language $B$ known to be non-regular to prove that a language $A$ is not regular.

My understanding is that the closure properties only apply when both languages are regular. So, I'm not sure what such a proof would look like and I'm looking for an outline of what the proof would look like.

Shaun
  • 44,997
EggHead
  • 667

1 Answers1

2

The class of regular languages is closed under intersection. Suppose that you can find a regular language $L$ such that $B=L\cap A$; if $A$ were regular, then $B$, being the intersection of two regular languages, would also be regular. However, we know that $B$ is not regular, so $A$ cannot be regular.

Other closure properties can be used in the same way.

Brian M. Scott
  • 616,228