Deterministic finite state machine

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 (dfa is for "deterministic finite automaton", another way to express it) - I think the code makes it pretty crystal-clear what's going on:

 proc dfa {description input} {
    foreach {states alphabet 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