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
