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:

R=lambda;
R belongs to I;
R=R1 U R2 or R=R1R2 where R1 and R2 are regular expressions on I;
R=R1* where R1 is a regular expression on I.
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.

On Formal Languages
Previous Sub-section

Back to Index