Version 1 of Deterministic finite state machine

Updated 2006-08-15 13:24:28 by suchenwi

Richard Suchenwirth 2006-08-15 - I'm not going to explain the concept here, http://en.wikipedia.org/wiki/Deterministic_finite_state_machine does it much better - but after reading that page, I had the irrepressible wish to implement one in Tcl, and as simple as could be. Here it is:


 proc dfa {description input} {
    foreach {states alph start accept transitions} $description break
    array set T $transitions
    set state $start
    foreach char [split $input ""] {
        set state $T($state,$char)
    }
    in $accept $state
 }
 #-- Little helper needed before we have 8.5's 'in' operator:
 proc in {list elem} {expr {[lsearch -exact $list $elem]>=0}}

# Now testing, with the example on that page that corresponds to the regular expression

 #  1*(01*01*)*

# i.e. any binary word with an even number of 0s

 set M {{S1 S2} {0 1} S1 S1 {
    S1,0 S2 S1,1 S1
    S2,0 S1 S2,1 S2}
 }    

 foreach test {00 11 101 01010 00100} {
    puts $test->[dfa $M $test]
 }

Produces:

 00->1
 11->1
 101->0
 01010->0
 00100->1

Category Example - Category Concept