A tutorial on finite automata


Regular Languages

We define regular languages as the smallest class of languages which contains all finite languages and closed with respect to union, concatenation and Kleene closure.

Any regular language can be denoted by a regular expression defined as follows.

Definition

If I is an alphabet, R is a regular expression over I if and only if it takes one of the following forms: Every regular expression denotes a regular language.

Example

(a*b) is a regular expression that denotes the set of strings formed by a sequence, also empty, of a's followed by a b.

Regular languages are recognized by finite automata and are generated by regular grammars.


Back to Index