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