Postal address
Department of Theoretical Physics, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India.
Secretariat phones
+91-22-2278 2244 +91-22-2278 2156
+91-22-2278 2777 +91-22-2280 4611 +91-22-2280 4610
Secretariat email
"theophys" The mailhost for DTP is

Please write to cmspjc at theory dot tifr dot res dot in for getting email announcements and any suggestions regarding CMSP Journal Club.

Condensed Matter and Statistical Physics Journal Club

Talk Details

Title Regular Expressions and Finite Automata
Speaker Abhay Parvate
Date Wed, 02 Feb 2011
Time 14:30
Venue A 304


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.