Prove that a Language is Non-Regular Using Closure Properties

3.2k Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.