We learned about the class of regular languages REG. It is characterised by any

Question

We learned about the class of regular languages REG. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a given language is regular.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all regular expressions (or for all finite automata, or for all left-linear grammars) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

This is intended to be a reference question collecting usual proof methods and application examples. See here for the same question on context-free languages.

Explanation / Answer

Proof by contradiction is often used to show that a language is not regular: let P a property true for all regular languages, if your specific language does not verify P, then it's not regular. The following properties can be used:

The pumping lemma, as exemplified in Dave's answer;
Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
A regular language has a finite number of prefix equivalence class, Myhill

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.