grammar::fa demo

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:

  • Click inside a state and drag into other state to make a new transition.
  • Use button 3 to delete a state or transition
  • Use shift-button1 to edit.

All variants of the automaton are automatically redrawn on each edit.

To use the simulation:

  • Enter text (must contain only symbols defined in fa) at the bottom
  • Press Reset
  • Then press Step for each step of simulation. Active states are highlighted, an underline in the text shows symbol to be read.

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