31-10-2012, 05:05 PM
Equivalence of Regular Language Representations
Equivalence of Regular.ppt (Size: 130.5 KB / Downloads: 58)
Construction of Regular Expression from Finite Automaton
Expression Graph is a labeled directed graph in which the arcs are labeled by regular expressions. An expression graph, like a state diagram, contains a distinguished start node and a set of accepting nodes.
Main Idea
To associate an RE with an FA,
reduce an arbitrary expression graph to one containing at most two nodes,
by repeatedly removing nodes from the graph and relabeling the arcs to preserve the language.
Without loss of generality, we can assume one accepting state (because of the presence of the union operation).