This is a demo program for tcllib's grammar::fa package.
It demonstrates drawing, editing & simulation of FAs. It further shows some functions of the package grammar::fa::ops.
Tcl 8.5 and Tcllib are required to run it.
There are 2 tabs: One for editing an automaton and one for its simulation on a given text.
The first tab displays, from top to bottom: source fa, then this fa without epsilon-transitions, then the equivalent deterministic FA, then this FA minimized.
Editing:
All variants of the automaton are automatically redrawn on each edit.
To use the simulation:
26.05.2009, Yaroslav Schekin (YS).
AK: This is really nice. A tiny bit of polish would be to have a help button which explains the use again, i.e. the button bindings listed above. I believe this would make a wonderful example to add to Tcllib.
package require Tcl 8.5
package require Tk
package require grammar::fa
package require grammar::fa::op
package require grammar::fa::dacceptor
package require grammar::fa::dexec
proc doit {} {
set ::G_widgets(CDraw) stub
MakeGui
::grammar::fa myfa
#fa_fill_random myfa 10 [list a b c d]
set RE {. {S d} {? {. {+ {S a}} {S d} {S a}}} {S a} {S b} \
{+ {. {S b} {S c}}} {S a}}
myfa fromRegex $RE
C_TabChanged
}
proc removeeps_simple {faName} {
#1. Calculate merged states:
set states [$faName states]
foreach state $states {
set e_clos [$faName epsilon_closure $state]
if {[llength $e_clos]>1} {
#Replace with merged state:
foreach rstate $e_clos {
#Merge rstate's transitions into current state:
if {$rstate in [$faName finalstates]} {
$faName final add $state
}
foreach symbol [$faName symbols] {
foreach nexts [$faName next $rstate $symbol] {
catch {$faName next $state $symbol --> $nexts}
}
}
}
}
}
#Remove epsilons from all states:
foreach state $states {
$faName !next $state {}
}
::grammar::fa::op::trim $faName !reachable
}
#Fills faName with random transitions, makes 'states' states
proc fa_fill_random {faName states symlist} {
$faName clear
foreach s $symlist {
$faName symbol add $s
}
set syms [llength $symlist]
set stnum 1
for {set f 0} {$f<$states} {incr f} {
$faName state add $stnum
set stnum [expr {$stnum*2}]
}
#Now wire it randomly:
set stnum 1
for {set f 0} {$f<$states-1} {incr f} {
#select symbol to use for next transition:
set trans [expr {int(rand()*$syms)}]
set nextst [expr {2*$stnum}]
$faName next $stnum [lindex $symlist $trans] --> $nextst
#Now epsilon transitions, absolutely random:
set trans [expr {int(rand()*2)}]
for {set t 0} {$t<$trans} {incr t} {
#Into random state:
set nextst [expr {2**(1+int(rand()*($states-1)))}]
catch {$faName next $stnum {} --> $nextst}
}
set stnum [expr {$stnum*2}]
}
$faName start add 1
set stnum [expr {$stnum/2}]
$faName final add $stnum
}
#. Layout the NFA (any NFA). IN ONE LINE!
# -- From THIS state TO any other can be ONLY one transition, BUT
# MANY symbols can be written on it.
# -- Must draw ARCS (smoothed lines) of defined height level.
# This level depends on interstate distance on the FA "line".
# -- Forward transitions are drawn OVER this "states line", backward
# transitions --- UNDER it.
# -- Forward transitions height 1 are drawn in the line: (0)->(1), backward
# transitions of height 1 --- at height -1: (0) (1)
# -- Self-transition is drawn specially (try to find best way).
proc DrawFa {faName c cx sy ssize sspace vlevel {noedit 0}} {
set nstates [lsort -integer [$faName states]]
set syms [$faName symbols]
set startstates [$faName startstates]
set finalstates [$faName finalstates]
set FSA_ID "F$faName"
lappend syms {}
set NumStates [llength $nstates]
# Just place start states at start, final at end:
set states $startstates
foreach state $nstates {
if {$state in $finalstates} continue
if {$state in $startstates} continue
lappend states $state
}
foreach fstate $finalstates {
if {$fstate in $states} continue
lappend states $fstate
}
set f 1
foreach state $states {
set Pos2State($f) $state
set State2Pos($state) $f
incr f
}
#2. Draw states as circles and output their numbers in them,
# remember states positions.
set cy 2000
set y1 [expr {$cy-$ssize}]
set y2 [expr {$cy+$ssize}]
for {set f 1} {$f<=$NumStates} {incr f} {
set SourceID "S$Pos2State($f)"
set TargetID "T$Pos2State($f)"
set taglst [list state $FSA_ID $SourceID $TargetID]
if {$noedit} {
lappend taglst NoEdit
}
set x1 [expr {$cx-$ssize}]
set x2 [expr {$cx+$ssize}]
if {$Pos2State($f) in $startstates} {
$c create oval $x1 $y1 $x2 $y2 -dash . -fill white \
-activefill gray \
-tags $taglst
} else {
$c create oval $x1 $y1 $x2 $y2 -fill white \
-activefill gray \
-tags $taglst
}
if {$Pos2State($f) in $finalstates} {
$c create oval [expr {$x1+3}] [expr {$y1+3}] \
[expr {$x2-3}] [expr {$y2-3}] -dash . \
-activefill gray \
-tags $taglst
}
$c create text $cx $cy -text $f \
-tags [concat txt $taglst]
set StatePosX($f) $cx
incr cx $sspace
}
#3. For each state in sorted order draw all its transitions,
# Must JOIN symbols in transitions into same state.
# Arc level is calculated trivially from relative states positions.
set minlevel 0
set maxlevel 0
for {set f 1} {$f<=$NumStates} {incr f} {
set SourceID "S$Pos2State($f)"
unset -nocomplain TransStates
set cstate $Pos2State($f)
set cXpos $StatePosX($f)
#Create 'nextstate => list of symbols' mapping:
foreach sym $syms {
set nextstates [$faName next $cstate $sym]
foreach ns $nextstates {
lappend TransStates($ns) $sym
}
}
#Must draw them, at last:
foreach {nstate symlst} [array get TransStates] {
set TargetID "T$nstate"
set trnstags [list trans $FSA_ID $SourceID $TargetID]
set color "black"
set txt [string map [list " " ,] $symlst]
set txt [string map [list {{}} {}] $txt]
set hlevel [expr {$State2Pos($nstate)-$f}]
if {$hlevel<$minlevel} {set minlevel $hlevel}
if {$hlevel>$maxlevel} {set maxlevel $hlevel}
set nXpos $StatePosX($State2Pos($nstate))
if {$hlevel==0} {
#self-transition:
set x1 [expr {$cXpos+3*$ssize/4}]
set x2 [expr {$cXpos+$ssize}]
set x3 [expr {$cXpos-$ssize}]
set x4 [expr {$cXpos-3*$ssize/4}]
set y1 [expr {$cy-3*$ssize/4}]
set y2 [expr {$cy-$vlevel-$ssize}]
$c create line $x1 $y1 $x2 $y2 $x3 $y2 $x4 $y1 \
-smooth 1 -arrow last -fill $color \
-tags $trnstags
$c create text $cXpos [expr {$y2-7}] -text $txt \
-tags [list $FSA_ID]
} elseif {$hlevel>0} {
if {$hlevel==1} {
#Only straight line:
set x1 [expr {$cXpos+$ssize}]
set x2 [expr {$cXpos+$sspace-$ssize}]
$c create line $x1 $cy $x2 $cy -arrow last -fill $color \
-tags $trnstags
$c create text [expr {$cXpos+$sspace/2}] [expr {$cy-7}] \
-text $txt \
-tags [list $FSA_ID]
} else {
#line forward:
set clevel [expr {$cy-$ssize-$vlevel*$hlevel}]
set y1 [expr {$cy-$ssize}]
set xlen [expr {$nXpos-$cXpos}]
#divide into 4 parts for line, into 2 for text:
set tx [expr {$cXpos+$xlen/2}]
set x2 [expr {$cXpos+$xlen/4}]
set x3 [expr {$cXpos+3*$xlen/4}]
$c create line $cXpos $y1 \
$x2 $clevel \
$x3 $clevel \
$nXpos $y1 -smooth 1 -arrow last -fill $color \
-tags $trnstags
$c create text $tx [expr {$clevel-7}] -text $txt \
-tags [list $FSA_ID]
}
} else {
#line backward:
set clevel [expr {$cy+$ssize-$vlevel*$hlevel}]
set y1 [expr {$cy+$ssize}]
set xlen [expr {$cXpos-$nXpos}]
#divide into 4 parts for line, into 2 for text:
set tx [expr {$cXpos-$xlen/2}]
set x2 [expr {$cXpos-$xlen/4}]
set x3 [expr {$cXpos-3*$xlen/4}]
$c create line $cXpos $y1 \
$x2 $clevel \
$x3 $clevel \
$nXpos $y1 -smooth 1 -arrow last -fill $color \
-tags $trnstags
$c create text $tx [expr {$clevel-7}] -text $txt \
-tags [list $FSA_ID]
}
}
}
incr maxlevel
set h [expr {($maxlevel-$minlevel)*$vlevel+3*$ssize}]
set mh [expr {$sy-2000+$maxlevel*$vlevel+$ssize}]
$c move $FSA_ID 0 $mh
return $h
}
proc C_zoomin {what} {
set ::G_scale [expr {$::G_scale*1.25}]
$what scale all 0 0 1.25 1.25
}
proc C_zoomout {what} {
set ::G_scale [expr {$::G_scale*0.8}]
$what scale all 0 0 0.8 0.8
}
proc MakeGui {} {
global G_widgets
package require Tk
package require tile
set ::G_scale 1.0
ttk::notebook .nb
frame .nb.ftabdraw
frame .nb.ftabdraw.fcanv
.nb add .nb.ftabdraw -text "NFA/DFA" -sticky news
.nb select .nb.ftabdraw
ttk::notebook::enableTraversal .nb
set G_widgets(CDraw) [canvas .nb.ftabdraw.fcanv.c -bg white \
-width 1024 -height 700 \
-scrollregion [list 0 0 10000 6000] \
-xscrollcommand {.nb.ftabdraw.fcanv.hscr set} \
-yscrollcommand {.nb.ftabdraw.fcanv.vscr set}]
$G_widgets(CDraw) bind state <Any-Enter> [list C_StateEnter $G_widgets(CDraw)]
$G_widgets(CDraw) bind state <Any-Leave> [list C_StateLeave $G_widgets(CDraw)]
$G_widgets(CDraw) bind state <1> [list C_NewTrans $G_widgets(CDraw) %x %y]
$G_widgets(CDraw) bind state <Shift-1> [list C_EditState $G_widgets(CDraw)]
$G_widgets(CDraw) bind state <3> [list C_DelState $G_widgets(CDraw)]
$G_widgets(CDraw) bind trans <3> [list C_DelTrans $G_widgets(CDraw)]
$G_widgets(CDraw) bind trans <Shift-1> [list C_EditTrans $G_widgets(CDraw)]
bind $G_widgets(CDraw) <B1-Motion> [list C_MoveTrans $G_widgets(CDraw) %x %y]
bind $G_widgets(CDraw) <ButtonRelease-1> \
[list C_EndTrans $G_widgets(CDraw) %x %y]
scrollbar .nb.ftabdraw.fcanv.hscr -orient horiz \
-command [list $G_widgets(CDraw) xview]
scrollbar .nb.ftabdraw.fcanv.vscr -command [list $G_widgets(CDraw) yview]
grid .nb.ftabdraw.fcanv.c .nb.ftabdraw.fcanv.vscr -sticky news
grid .nb.ftabdraw.fcanv.hscr -sticky news
grid columnconfigure .nb.ftabdraw.fcanv 0 -weight 1
grid rowconfigure .nb.ftabdraw.fcanv 0 -weight 1
frame .nb.ftabdraw.fbuttons
button .nb.ftabdraw.fbuttons.bzoom -text "Zoom in" \
-command [list C_zoomin $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.bunzoom -text "Zoom out" \
-command [list C_zoomout $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.baddstate -text "Add state" \
-command [list C_addstate $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.bsave -text "Save" \
-command [list C_saveNFA]
button .nb.ftabdraw.fbuttons.bload -text "Load" \
-command [list C_loadNFA $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.breverse -text "Reverse" \
-command [list C_ReverseNFA $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.bremeps -text "Remove eps" \
-command [list C_RemoveEps $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.bdeterm -text "Determinize" \
-command [list C_DeterminNFA $G_widgets(CDraw)]
button .nb.ftabdraw.fbuttons.bmin -text "Minimize" \
-command [list C_MinNFA $G_widgets(CDraw)]
grid .nb.ftabdraw.fbuttons.bzoom -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bunzoom -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.baddstate -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bsave -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bload -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.breverse -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bremeps -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bdeterm -sticky news -padx 1 -pady 1
grid .nb.ftabdraw.fbuttons.bmin -sticky news -padx 1 -pady 1
label .nb.ftabdraw.lstatus -text "Status:"
set G_widgets(Status1) \
[entry .nb.ftabdraw.estatus -bg white -text "status line"]
grid .nb.ftabdraw.fbuttons .nb.ftabdraw.fcanv -sticky news
grid .nb.ftabdraw.lstatus .nb.ftabdraw.estatus -sticky news
grid .nb -sticky news
grid columnconfigure . 0 -weight 1
grid rowconfigure . 0 -weight 1
grid columnconfigure .nb 0 -weight 1
grid rowconfigure .nb 0 -weight 1
grid columnconfigure .nb.ftabdraw 1 -weight 1
grid rowconfigure .nb.ftabdraw 0 -weight 1
#==========================================================================
frame .nb.fmultisim
.nb add .nb.fmultisim -text "Multistate simulation"
frame .nb.fmultisim.fcanv
set G_widgets(CMSim) [canvas .nb.fmultisim.fcanv.c -bg white \
-width 1024 -height 700 \
-scrollregion [list 0 0 10000 6000] \
-xscrollcommand {.nb.fmultisim.fcanv.hscr set} \
-yscrollcommand {.nb.fmultisim.fcanv.vscr set}]
$G_widgets(CMSim) bind state <Any-Enter> [list C_StateEnter $G_widgets(CMSim)]
$G_widgets(CMSim) bind state <Any-Leave> [list C_StateLeave $G_widgets(CMSim)]
scrollbar .nb.fmultisim.fcanv.hscr -orient horiz \
-command [list $G_widgets(CMSim) xview]
scrollbar .nb.fmultisim.fcanv.vscr -command [list $G_widgets(CMSim) yview]
grid .nb.fmultisim.fcanv.c .nb.fmultisim.fcanv.vscr -sticky news
grid .nb.fmultisim.fcanv.hscr -sticky news
grid columnconfigure .nb.fmultisim.fcanv 0 -weight 1
grid rowconfigure .nb.fmultisim.fcanv 0 -weight 1
frame .nb.fmultisim.fbuttons
button .nb.fmultisim.fbuttons.bzoom -text "Zoom in" \
-command [list C_zoomin $G_widgets(CMSim)]
button .nb.fmultisim.fbuttons.bunzoom -text "Zoom out" \
-command [list C_zoomout $G_widgets(CMSim)]
button .nb.fmultisim.fbuttons.bmsimstep -text "Step" \
-command [list C_MSimStep $G_widgets(CMSim)]
button .nb.fmultisim.fbuttons.bmsimreset -text "Reset" \
-command [list C_MsimReset $G_widgets(CMSim)]
grid .nb.fmultisim.fbuttons.bzoom -sticky news -padx 1 -pady 1
grid .nb.fmultisim.fbuttons.bunzoom -sticky news -padx 1 -pady 1
grid .nb.fmultisim.fbuttons.bmsimstep -sticky news -padx 1 -pady 1
grid .nb.fmultisim.fbuttons.bmsimreset -sticky news -padx 1 -pady 1
label .nb.fmultisim.lstatus -text "Text:"
set G_widgets(MSimText) \
[text .nb.fmultisim.tstatus -bg white -width 60 -height 1]
grid .nb.fmultisim.fbuttons .nb.fmultisim.fcanv -sticky news -pady 2
grid .nb.fmultisim.lstatus .nb.fmultisim.tstatus -sticky news -pady 2
grid columnconfigure .nb.fmultisim 1 -weight 1
grid rowconfigure .nb.fmultisim 0 -weight 1
bind .nb <<NotebookTabChanged>> C_TabChanged
}
proc C_StateEnter {c} {
set StateSrc [lsearch -inline [$c gettags current] S*]
set FSA_ID [lsearch -inline [$c gettags current] F*]
$c itemconfigure ($FSA_ID&&$StateSrc&&!state) -fill green
$c raise ($FSA_ID&&$StateSrc&&!state)
return
}
proc C_StateLeave {c} {
set StateSrc [lsearch -inline [$c gettags current] S*]
set FSA_ID [lsearch -inline [$c gettags current] F*]
$c itemconfigure ($FSA_ID&&$StateSrc&&!state) -fill black
return
}
proc C_NewTrans {c x y} {
set x [$c canvasx $x]; set y [$c canvasy $y]
if {[lsearch -exact [$c gettags current] NoEdit]>=0} return
set StateSrc [lsearch -inline [$c gettags current] S*]
set FSA_ID [lsearch -inline [$c gettags current] F*]
$c create line $x $y $x $y -fill red \
-tags [list aline $FSA_ID $StateSrc] -arrow last
return
}
proc C_MoveTrans {c x y} {
set x [$c canvasx $x]; set y [$c canvasy $y]
#If exists aline:
set lineid [$c find withtag aline]
if {$lineid eq ""} return
set coords [$c coords $lineid]
lset coords 2 $x ; lset coords 3 $y
$c coords $lineid $coords
return
}
proc C_EndTrans {c x y} {
set x [$c canvasx $x]; set y [$c canvasy $y]
#If exists aline:
set lineid [$c find withtag aline]
if {$lineid eq ""} return
set ltags [$c gettags aline]
set StateSrc [lsearch -inline $ltags S*]
set FSA_ID [lsearch -inline $ltags F*]
$c delete aline
#Now must find out if we are in some state of the SAME FSA:
set IDs [$c find overlapping $x $y $x $y]
foreach ID $IDs {
set tags [$c gettags $ID]
if {[lsearch $tags $FSA_ID]==-1} continue
if {[lsearch $tags state]>=0} {
#Some state found, process it, create new (epsilon) transition!
set StateTgt [lsearch -inline $tags T*]
set numS [string range $StateSrc 1 end]
set numT [string range $StateTgt 1 end]
set faName [string range $FSA_ID 1 end]
catch {$faName next $numS {} --> $numT}
DrawAllFa $faName $c
break
}
}
return
}
#Delete current transition:
proc C_DelTrans {c} {
set tags [$c gettags current]
set FSA_ID [lsearch -inline $tags F*]
set StateSrc [lsearch -inline $tags S*]
set StateTgt [lsearch -inline $tags T*]
set numS [string range $StateSrc 1 end]
set numT [string range $StateTgt 1 end]
set faName [string range $FSA_ID 1 end]
catch {$faName !next $numS {} --> $numT}
foreach s [$faName symbols] {
catch {$faName !next $numS $s --> $numT}
}
DrawAllFa $faName $c
return
}
#Delete current state:
proc C_DelState {c} {
set tags [$c gettags current]
set FSA_ID [lsearch -inline $tags F*]
set StateSrc [lsearch -inline $tags S*]
set numS [string range $StateSrc 1 end]
set faName [string range $FSA_ID 1 end]
$faName state delete $numS
DrawAllFa $faName $c
return
}
proc C_addstate {c} {
set states [lsort -dictionary [myfa states]]
set newstate [expr {[lindex $states end]+1}]
myfa state add $newstate
DrawAllFa myfa $c
return
}
proc C_EditState {c} {
set tags [$c gettags current]
set FSA_ID [lsearch -inline $tags F*]
set StateSrc [lsearch -inline $tags S*]
set numS [string range $StateSrc 1 end]
set faName [string range $FSA_ID 1 end]
set reply [tk_dialog .foo "Edit State" "Choose state type" \
questhead 0 Ordinary Start Final Start+Final]
$faName final remove $numS
$faName start remove $numS
if {$reply & 1} {
$faName start add $numS
}
if {$reply & 2} {
$faName final add $numS
}
DrawAllFa myfa $c
return
}
proc sym_dialog {symlst} {
global G_Dialog
set G_Dialog $symlst
set w [toplevel .syms_Dialog]
wm resizable $w 0 0
wm title $w "Enter values"
label $w.l -text "Symbols:"
entry $w.e -textvar G_Dialog -bg white
bind $w.e <Return> {set done 1}
button $w.ok -text OK -command {set done 1}
button $w.c -text Clear -command [list set G_Dialog {}]
button $w.cancel -text Cancel -command "set G_Dialog {}; set done 1"
grid $w.l - - -sticky news
grid $w.e - - -sticky news
grid $w.ok $w.c $w.cancel
vwait done
destroy $w
return $G_Dialog
}
proc C_EditTrans {c} {
set tags [$c gettags current]
set FSA_ID [lsearch -inline $tags F*]
set StateSrc [lsearch -inline $tags S*]
set StateTgt [lsearch -inline $tags T*]
set numS [string range $StateSrc 1 end]
set numT [string range $StateTgt 1 end]
set faName [string range $FSA_ID 1 end]
#Must ask for a list of symbols now, and make transtions.
set symlst [$faName symbols]
lappend symlst ""
set syms [list]
foreach sym $symlst {
set nextstates [$faName next $numS $sym]
if {[lsearch -exact $nextstates $numT] >= 0} {
lappend syms $sym
}
}
set syms [sym_dialog $syms]
if {$syms eq ""} return
set symbols [$faName symbols]
lappend symbols ""
foreach s $symbols {
catch {$faName !next $numS $s --> $numT}
}
foreach s [lsort -unique $syms] {
if {[lsearch -exact $symbols $s]==-1} {
$faName symbol add $s
}
catch {$faName next $numS $s --> $numT}
}
DrawAllFa $faName $c
return
}
#Save myfa into selected file.
proc C_saveNFA {} {
set types {{{Text Files} {.txt}} {{All Files} * }}
set fname [tk_getSaveFile -defaultextension ".txt" -filetypes $types]
if {$fname eq ""} return
set fd [open $fname w]
puts $fd [myfa serialize]
close $fd
}
#Load myfa from selected file.
proc C_loadNFA {c} {
set types {{{Text Files} {.txt}} {{All Files} * }}
set fname [tk_getOpenFile -defaultextension ".txt" -filetypes $types]
if {$fname eq ""} return
set fd [open $fname]
myfa clear
myfa deserialize [read $fd]
close $fd
DrawAllFa myfa $c
}
proc C_ReverseNFA {c} {
myfa reverse
DrawAllFa myfa $c
}
proc C_RemoveEps {c} {
removeeps_simple myfa
DrawAllFa myfa $c
}
proc C_DeterminNFA {c} {
myfa determinize
DrawAllFa myfa $c
}
proc C_MinNFA {c} {
myfa minimize
DrawAllFa myfa $c
}
proc C_TabChanged {} {
global G_widgets
set tnum [.nb index current]
if {$tnum == 0} {
DrawAllFa myfa $G_widgets(CDraw)
}
if {$tnum == 1} {
$G_widgets(CMSim) delete all
DrawFa myfa $G_widgets(CMSim) 30 20 20 80 20 1
$G_widgets(CMSim) scale all 0 0 $::G_scale $::G_scale
C_MsimReset $G_widgets(CMSim)
}
return
}
#Here G_MsimStates is a list of active states in the same
#sequence as returned from [lsort -dictionary [myfa states]]
proc C_MSimStep {c} {
global G_MsimIndex G_MsimStates G_widgets
#Get current symbol:
set sym [$G_widgets(MSimText) get 1.$G_MsimIndex]
set states [lsort -dictionary [myfa states]]
set f 0
foreach state $states {
set State2TmpPos($state) $f
lappend tmpstates 0
incr f
}
#Make e-closures first:
foreach state $states active $G_MsimStates {
if {$active} {
set e_clos [myfa epsilon_closure $state]
foreach ns $e_clos {
lset G_MsimStates $State2TmpPos($ns) 1
}
}
}
#Check current symbol then:
foreach state $states active $G_MsimStates {
if {$active} {
foreach ns [myfa next $state $sym] {
lset tmpstates $State2TmpPos($ns) 1
}
}
}
set G_MsimStates $tmpstates
incr G_MsimIndex
#Must display it, now. Turn off all states:
$c itemconfigure (state&&!txt) -fill white
foreach state $states active $G_MsimStates {
if {$active} {
$c itemconfigure (S$state&&state&&!txt) -fill green
}
}
#Highlight new text position:
$G_widgets(MSimText) tag delete myactive
$G_widgets(MSimText) tag add myactive 1.$G_MsimIndex
$G_widgets(MSimText) tag configure myactive -underline 1
return
}
#Activate all start states:
proc C_MsimReset {c} {
global G_MsimIndex G_MsimStates G_widgets
$c itemconfigure (state&&!txt) -fill white
set G_MsimIndex 0
unset -nocomplain G_MsimStates
set starts [myfa startstates]
set states [lsort -dictionary [myfa states]]
foreach state $states {
if {$state in $starts} {
lappend G_MsimStates 1
$c itemconfigure (S$state&&state&&!txt) -fill green
} else {
lappend G_MsimStates 0
}
}
$G_widgets(MSimText) tag delete myactive
$G_widgets(MSimText) tag add myactive 1.0
$G_widgets(MSimText) tag configure myactive -underline 1
return
}
#========================================================================
#This must draw, for given NFA, its no-eps, dfa and min-dfa versions.
proc DrawAllFa {faname c} {
catch {noeps destroy}
catch {dfa destroy}
catch {minfa destroy}
$c delete all
set ch 20
set h [DrawFa $faname $c 30 $ch 20 80 20 0]
set ch [expr {$ch+$h}]
$c create line 0 $ch 10000 $ch
grammar::fa noeps = $faname
removeeps_simple noeps
set h [DrawFa noeps $c 30 $ch 20 80 20 1]
set ch [expr {$ch+$h}]
$c create line 0 $ch 10000 $ch
grammar::fa dfa = noeps
dfa determinize mapvar
set h [DrawFa dfa $c 30 $ch 20 80 20 1]
set ch [expr {$ch+$h}]
$c create line 0 $ch 10000 $ch
grammar::fa minfa = dfa
minfa minimize mapvar
set h [DrawFa minfa $c 30 $ch 20 80 20 1]
set ch [expr {$ch+$h}]
$c create line 0 $ch 10000 $ch
$c scale all 0 0 $::G_scale $::G_scale
}
doit