def transition_table
dtrans = TransitionTable.new
marked = {}
state_id = Hash.new { |h,k| h[k] = h.length }
start = firstpos(root)
dstates = [start]
until dstates.empty?
s = dstates.shift
next if marked[s]
marked[s] = true
s.group_by { |state| symbol(state) }.each do |sym, ps|
u = ps.map { |l| followpos(l) }.flatten
next if u.empty?
if u.uniq == [DUMMY]
from = state_id[s]
to = state_id[Object.new]
dtrans[from, to] = sym
dtrans.add_accepting to
ps.each { |state| dtrans.add_memo to, state.memo }
else
dtrans[state_id[s], state_id[u]] = sym
if u.include? DUMMY
to = state_id[u]
accepting = ps.find_all { |l| followpos(l).include? DUMMY }
accepting.each { |accepting_state|
dtrans.add_memo to, accepting_state.memo
}
dtrans.add_accepting state_id[u]
end
end
dstates << u
end
end
dtrans
end