January 27th, 2012
Algorithms for Regular Languages
Theorem 3.1 - Given L in standard representation and w 2 ▯ , there is an
algorithm for determining whether w 2 L.
Assume w:l:o:g: that L is given by a DFA M with L(M) = L. Let G(M) be the
state transition graph of M.
L 6= ; , in G(M) there is a path from the intial state to the ▯nal state.
! Use depth-▯rst search to check whether G(M) has such a path.
L is in▯nite, , G(M) contains a cycle C, and there is a path from the initial state
to C and a path from C to a ▯nal state.
Theorem 3.3 - There exists an algorithm for determining whether two regular
languages L 1L 2 given in a standard representation, are equal.
Let M ie a DFA for L , i 2 f1;2g.
Let L = (L 1 L )2_ (L ^1L ).2
Then L = L , L = ;.
Using the constructions from the proof of Threorem ??, we construct an NFA N
Convert N into an equivalent DFA M.
We can use this DFA to show the algorithm exists. ▯
Regular languages are not powerful enough to describe languages such as pro-
E:g:: A syntactically correct p