Proof of Correctness of a Direct Construction of DFA from Regular Expression

Abstract

We present a proof of correctness of an algorithm for directly constructing a deterministic finite automaton (DFA) from a regular expression. We do this in a functional framework by introducing a structure called dot annotated regular expression (dare). A dare acts as an implicit representation of a state in a DFA. State transitions in a DFA correspond to dot movements in a dare. We investigate and identify certain algebraic properties of dares which are then used to prove the correctness of the algorithm. The proof is algebraic and presented in the same framework as that of the algorithm itself.

Keywords:

• Correctness of algorithm
• recognition problem
• regular expressions
• finite automata

C.R.Categories:

• D.1.1
• D.3.1
• F.1.1
• F.3.1