Record Details

Proof of correctness of a direct construction of DFA from regular expression

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Proof of correctness of a direct construction of DFA from regular expression
 
Creator BABU, SR
SANYAL, A
VENKATESH, G
 
Subject correctness of algorithm
recognition problem
regular expressions
finite automata
 
Description 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 dare's 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.
 
Publisher GORDON BREACH SCI PUBL LTD
 
Date 2011-07-31T05:05:37Z
2011-12-26T12:52:50Z
2011-12-27T05:39:45Z
2011-07-31T05:05:37Z
2011-12-26T12:52:50Z
2011-12-27T05:39:45Z
1997
 
Type Article
 
Identifier INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 64(3-4), 191-210
0020-7160
http://dx.doi.org/10.1080/00207169708804584
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7993
http://hdl.handle.net/10054/7993
 
Language en