Regular Expressions and Finite Automata

Regular Expressions play an all-pervading role in computation. For the purpose of checking whether a given sequence falls in the language described by a regular expression (matching), they are usually converted into finite automata.

The talk will begin by defining regular expressions and finite automata. An algorithm given by Berri and Sethi (1986) for converting regular expressions into nondeterministic finite automata will be discussed.

A transformation of regular expression into the so-called Star-Normal Form (Bruggmann-Klein, 1993) will be discussed. It turns out that the above algorithm has improved time efficiency once a regular expression is in this form.

A compressed representation of nondeterministic finite automata will be discussed, which further improves space and time requirements. It is also expected that it will improve the "matching" time.