[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]