Regular Expressions

This note deals with regular expressions recognition of formal languages. For practical use of regular expressions in programming, see regex.

Definition

Regular expressions are another way of specifying the same languages that can be specified by DFAs and NFAs. A regular expression over an alphabet is defined according to the following rules:

Regular Expression	Language





(Kleene star)	(split into parts )

Examples

strings containing aa as a substring: