Version 1 of grammar::fa demo

Updated 2009-05-26 16:23:17 by AK

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 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 then 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).

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