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