Deterministic finite state machine

A deterministic finite state machine is a kind of Finite State Machine.

Richard Suchenwirth 2006-08-15 - I'm not going to explain the concept here - this wikipedia page 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