class Journey::NFA::TransitionTable
Attributes
accepting[RW]
memos[R]
Public Class Methods
new()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 11 def initialize @table = Hash.new { |h,f| h[f] = {} } @memos = {} @accepting = nil @inverted = nil end
Public Instance Methods
[]=(i, f, s)
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 34 def []= i, f, s @table[f][i] = s end
accepting?(state)
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 18 def accepting? state accepting == state end
accepting_states()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 22 def accepting_states [accepting] end
add_memo(idx, memo)
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 26 def add_memo idx, memo @memos[idx] = memo end
alphabet()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 111 def alphabet inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.to_s } end
eclosure(t)
click to toggle source
Returns a set of NFA
states reachable from some NFA
state s
in set t
on nil-transitions alone.
# File lib/journey/nfa/transition_table.rb, line 118 def eclosure t stack = Array(t) seen = {} children = [] until stack.empty? s = stack.pop next if seen[s] seen[s] = true children << s stack.concat inverted[s][nil] end children.uniq end
following_states(t, a)
click to toggle source
Returns set of NFA
states to which there is a transition on ast symbol a
from some state s
in t
.
# File lib/journey/nfa/transition_table.rb, line 96 def following_states t, a Array(t).map { |s| inverted[s][a] }.flatten.uniq end
generalized_table()
click to toggle source
Returns a generalized transition graph with reduced states. The states are reduced like a DFA, but the table must be simulated like an NFA
.
Edges of the GTG
are regular expressions
# File lib/journey/nfa/transition_table.rb, line 52 def generalized_table gt = GTG::TransitionTable.new marked = {} state_id = Hash.new { |h,k| h[k] = h.length } alphabet = self.alphabet stack = [eclosure(0)] until stack.empty? state = stack.pop next if marked[state] || state.empty? marked[state] = true alphabet.each do |alpha| next_state = eclosure(following_states(state, alpha)) next if next_state.empty? gt[state_id[state], state_id[next_state]] = alpha stack << next_state end end final_groups = state_id.keys.find_all { |s| s.sort.last == accepting } final_groups.each do |states| id = state_id[states] gt.add_accepting id save = states.find { |s| @memos.key?(s) && eclosure(s).sort.last == accepting } gt.add_memo id, memo(save) end gt end
memo(idx)
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 30 def memo idx @memos[idx] end
merge(left, right)
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 38 def merge left, right @memos[right] = @memos.delete left @table[right] = @table.delete(left) end
move(t, a)
click to toggle source
Returns set of NFA
states to which there is a transition on ast symbol a
from some state s
in t
.
# File lib/journey/nfa/transition_table.rb, line 103 def move t, a Array(t).map { |s| inverted[s].keys.compact.find_all { |sym| sym === a }.map { |sym| inverted[s][sym] } }.flatten.uniq end
states()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 43 def states (@table.keys + @table.values.map(&:keys).flatten).uniq end
transitions()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 136 def transitions @table.map { |to, hash| hash.map { |from, sym| [from, sym, to] } }.flatten(1) end
Private Instance Methods
inverted()
click to toggle source
# File lib/journey/nfa/transition_table.rb, line 143 def inverted return @inverted if @inverted @inverted = Hash.new { |h,from| h[from] = Hash.new { |j,s| j[s] = [] } } @table.each { |to, hash| hash.each { |from, sym| if sym sym = Nodes::Symbol === sym ? sym.regexp : sym.left end @inverted[from][sym] << to } } @inverted end