Object
# File lib/journey/nfa/transition_table.rb, line 34 def []= i, f, s @table[f][i] = s end
# File lib/journey/nfa/transition_table.rb, line 18 def accepting? state accepting == state end
# File lib/journey/nfa/transition_table.rb, line 22 def accepting_states [accepting] end
# File lib/journey/nfa/transition_table.rb, line 26 def add_memo idx, memo @memos[idx] = memo end
# 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
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
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
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
# File lib/journey/nfa/transition_table.rb, line 30 def memo idx @memos[idx] end
# File lib/journey/nfa/transition_table.rb, line 38 def merge left, right @memos[right] = @memos.delete left @table[right] = @table.delete(left) end
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
Generated with the Darkfish Rdoc Generator 2.