Regular Language
Definition. A language is regular if some DFA recognizes it, that is, if it is for some DFA .
By the subset construction this is the same as being recognized by some NFA, so either model may be used to show a language is regular, and the NFA is usually the smaller one to write down. Showing a language is not regular needs a different tool, since no single machine can be exhibited; that is the pumping lemma in Lecture 4. Introduced in Lecture 3.