Class: Journey::NFA::TransitionTable

Inherits:
Object
  • Object
show all
Includes:
Dot
Defined in:
lib/journey/nfa/transition_table.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Dot

#to_dot

Constructor Details

#initialize ⇒ TransitionTable

Returns a new instance of TransitionTable.



11
12
13
14
15
16
 
# File 'lib/journey/nfa/transition_table.rb', line 11

def initialize
  @table     = Hash.new { |h,f| h[f] = {} }
  @memos     = {}
  @accepting = nil
  @inverted  = nil
end

Instance Attribute Details

#accepting ⇒ Object

Returns the value of attribute accepting.



8
9
10
 
# File 'lib/journey/nfa/transition_table.rb', line 8

def accepting
  @accepting
end

#memos ⇒ Object (readonly)

Returns the value of attribute memos.



9
10
11
 
# File 'lib/journey/nfa/transition_table.rb', line 9

def memos
  @memos
end

Instance Method Details

#[]=(i, f, s) ⇒ Object 



34
35
36
 
# File 'lib/journey/nfa/transition_table.rb', line 34

def []= i, f, s
  @table[f][i] = s
end

#accepting?(state) ⇒ Boolean

Returns:

  • (Boolean) 


18
19
20
 
# File 'lib/journey/nfa/transition_table.rb', line 18

def accepting? state
  accepting == state
end

#accepting_states ⇒ Object 



22
23
24
 
# File 'lib/journey/nfa/transition_table.rb', line 22

def accepting_states
  [accepting]
end

#add_memo(idx, memo) ⇒ Object 



26
27
28
 
# File 'lib/journey/nfa/transition_table.rb', line 26

def add_memo idx, memo
  @memos[idx] = memo
end

#alphabet ⇒ Object 



111
112
113
 
# 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) ⇒ Object

Returns a set of NFA states reachable from some NFA state s in set t on nil-transitions alone.



118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# 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) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.



96
97
98
 
# 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 ⇒ Object

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



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# 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) ⇒ Object 



30
31
32
 
# File 'lib/journey/nfa/transition_table.rb', line 30

def memo idx
  @memos[idx]
end

#merge(left, right) ⇒ Object 



38
39
40
41
 
# 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) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.



103
104
105
106
107
108
109
 
# 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 ⇒ Object 



43
44
45
 
# File 'lib/journey/nfa/transition_table.rb', line 43

def states
  (@table.keys + @table.values.map(&:keys).flatten).uniq
end

#transitions ⇒ Object 



136
137
138
139
140
 
# 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