class ToknInternal::State

A state within a state machine (NFA or DFA); also, various utility functions for manipulating state machines. Observe that a state machine can be referred to by its start state.

Each state has a set of directed edges to other states, where each edge is labelled with a CodeSet.

It also has a unique id (unique within a particular state machine), and a (boolean) final state flag.

For debug purposes, both the state and its edges can be labelled.

Attributes

edges[R]

Edges are a list of [label:CharSetRange, dest:State] pairs

finalState[RW]
finalState?[RW]
id[RW]
label[RW]

Public Class Methods

dumpNFA(st) click to toggle source

Produce a readable description of an NFA, for debug purposes

> st start state

# File lib/tokn/state.rb, line 32
def self.dumpNFA(st)
  str = "NFA:\n"
  map,_,_ = st.reachableStates
  map.each do |s| 
    str += " "+d(s)+"\n"
    str += "  edges= "+d(s.edges)+"\n"
    s.edges.each{ |lbl,dest| str += "   "+d(lbl)+"  ==> "+d(dest)+"\n"}
  end
  str
end
new(id) click to toggle source
# File lib/tokn/state.rb, line 51
def initialize(id) 
  @edges = [] 
  @id = id
end
normalizeStates(startState) click to toggle source

Normalize a state machine.

For each state:

[] merge edges that go to a common state
[] delete edges that have empty labels
[] sort edges by destination state ids

> start state

# File lib/tokn/state.rb, line 96
def self.normalizeStates(startState)
  stateSet, _,_ = startState.reachableStates
  stateSet.map{|s| s.normalize}
end

Public Instance Methods

addEdge(codeSet,destState) click to toggle source

Add an edge

codeSet : the character codes to label it with
destState : destination state
# File lib/tokn/state.rb, line 64
def addEdge(codeSet,destState)
  @edges.push([codeSet, destState])
end
addEps(destState) click to toggle source

Add a e-transition edge

destState : destination state
# File lib/tokn/state.rb, line 71
def addEps(destState)
  addEdge(CodeSet.new(EPSILON), destState)
end
clearEdges() click to toggle source
# File lib/tokn/state.rb, line 56
def clearEdges
  @edges.clear
end
duplicateNFA(dupBaseId = nil) click to toggle source

Duplicate the NFA reachable from this state, possibly with new ids

> dupBaseId : lowest id to use for duplicate; if nil, uses

next available id

< [ map of original states => duplicate states;

1 + highest id in new NFA ]
# File lib/tokn/state.rb, line 198
def duplicateNFA(dupBaseId = nil)
  oldStates, oldMinId, oldMaxId = reachableStates()
  dupBaseId ||= oldMaxId
  
   
  oldToNewStateMap = {}
  
  oldStates.each do |s|
    s2 = State.new((s.id - oldMinId) + dupBaseId)
    s2.finalState = s.finalState?
    s2.label = s.label
    
    oldToNewStateMap[s] = s2
  end
  
  oldStates.each do |s|
    s2 = oldToNewStateMap[s]
    s.edges.each{ |lbl,dest|  s2.addEdge(lbl, oldToNewStateMap[dest])}
  end
  
  [oldToNewStateMap, (oldMaxId - oldMinId) + dupBaseId]
end
eql?(other) click to toggle source
# File lib/tokn/state.rb, line 47
def eql?(other)
  return id == other.id
end
generatePDF(dir = nil, title = "nfa") click to toggle source

Generate a PDF of the state machine; Makes a system call to the dot utility to convert a .dot file to a .pdf

# File lib/tokn/state.rb, line 105
def generatePDF(dir = nil, title = "nfa")
  stateList = {}
  
  startState = self
  genAux( stateList, startState)
  
  g = ""
  g += "digraph "+title+" {\n"
  g += " '' [shape=none]\n"
  
  stateList.each_value do |s| 
    g += " '" + s.name + "' [shape="
    if s.finalState?
      g += "doubleoctagon"
    else
      g += "octagon"
    end
    g += "]\n"
  end

  g += "\n"
  g += " '' -> '" + startState.name + "'\n"
  stateList.each_value do |s| 
    s.edges.each do |crs, s2|
      g += " '"+s.name+"' -> '" + s2.name + "' [label='"
      g += d(crs)
      g += "'][fontname=Courier][fontsize=12]\n"
    end
  end

  g += "\n}\n"
  g.gsub!( /'/, '"' )
  
  dotToPDF(g,title,dir)
end
hash() click to toggle source
# File lib/tokn/state.rb, line 43
def hash
  return @id
end
inspect() click to toggle source
# File lib/tokn/state.rb, line 75
def inspect   
  name
end
name() click to toggle source
# File lib/tokn/state.rb, line 79
def name
  nm = 'S' + d(id)
  if label
    nm += ": "+label
  end
  nm
end
normalize() click to toggle source

Normalize a state

[] merge edges that go to a common state
[] delete edges that have empty labels
[] sort edges by destination state ids
# File lib/tokn/state.rb, line 148
def normalize()
  
  db = false
  
  !db || pr("\n\nnormalize state:\n  %s\nedges=\n%s\n",d(self),d(@edges))
  
  @edges.sort!{|x,y| 
    label1,dest1 = x
    label2,dest2 = y
    dest1.id <=> dest2.id
  }
  !db || pr(" sorted edges: %s\n",d(@edges))
  
  newEdges = []
  prevLabel, prevDest = nil,nil
  
  edges.each do |label,dest|
    !db || pr("  processing edge  %s,  %s\n",d(label),d(dest))
  
    if prevDest and prevDest.id == dest.id
      # changed = true
      !db || pr("    adding set %s to prevLabel %s...\n",d(label),d(prevLabel))
      prevLabel.addSet(label)
      !db || pr("    ...now %s\n",d(prevLabel))
    else
      if prevDest
        newEdges.push([prevLabel,prevDest])
      end
      # Must start a fresh copy!  Don't want to modify the original label.
      prevLabel = label.makeCopy()
      prevDest = dest
      !db || pr("    pushed onto new edges\n")  
      end
    end
    if prevDest
       newEdges.push([prevLabel,prevDest])
    end
          
  @edges = newEdges
  !db || pr("edges now: %s\n",d(@edges))
end
reachableStates() click to toggle source

Build set of states reachable from this state

> list of starting states < [ set, set of states reachable from those states

  minId, lowest id in set
  maxId    1 + highest id in set
]
# File lib/tokn/state.rb, line 276
def reachableStates()
  set = Set.new
  stack = []
  stack.push(self)
  
  maxId = nil
  minId = nil
  
  while !stack.empty?
    st = stack.pop
    set.add(st)
    
    if !minId || minId > st.id
      minId = st.id
    end
    if !maxId || maxId <= st.id
      maxId = 1 + st.id
    end
    
    st.edges.each do |lbl, dest|
      if set.add?(dest)
        stack.push(dest)
      end
    end
  end
  [set, minId,  maxId]
end
reverseNFA() click to toggle source

Construct the reverse of the NFA starting at this state < start state of reversed NFA

# File lib/tokn/state.rb, line 226
def reverseNFA()
  
  stateSet, minId, maxId = reachableStates()
  
  edgeList = []
  
  newStartStateList = []
  newFinalStateList = []
  
  newStateMap = {}
  
  stateSet.each do |s|
      
    u = State.new(s.id)
    newStateMap[u.id] = u
    
    if s.id == self.id
      newFinalStateList.push(u)
      u.finalState = true
    end
    
    if s.finalState?
      newStartStateList.push(u)
    end
    
    s.edges.each {|lbl, dest| edgeList.push([dest.id, s.id, lbl])}
    
  end
  
  edgeList.each do |srcId, destId, lbl|
    srcState = newStateMap[srcId]
    destState = newStateMap[destId]
    srcState.addEdge(lbl, destState)  
  end
  
  # Create a distinguished start node that points to each of the start nodes
  w = State.new(maxId)
  newStartStateList.each {|s| w.addEps(s)}  
  w
end

Private Instance Methods

genAux(stateList, st) click to toggle source
# File lib/tokn/state.rb, line 307
def genAux(stateList, st)
  if not stateList.member?(st.name)
    stateList[st.name] = st
    st.edges.each {|label, dest| genAux(stateList, dest)}
  end
end