1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
require 'journey/nfa/dot'
module Journey
module NFA
class TransitionTable
include Journey::NFA::Dot
attr_accessor :accepting
attr_reader :memos
def initialize
@table = Hash.new { |h,f| h[f] = {} }
@memos = {}
@accepting = nil
@inverted = nil
end
def accepting? state
accepting == state
end
def accepting_states
[accepting]
end
def add_memo idx, memo
@memos[idx] = memo
end
def memo idx
@memos[idx]
end
def []= i, f, s
@table[f][i] = s
end
def merge left, right
@memos[right] = @memos.delete left
@table[right] = @table.delete(left)
end
def states
(@table.keys + @table.values.map(&:keys).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
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
###
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
def following_states t, a
Array(t).map { |s| inverted[s][a] }.flatten.uniq
end
###
# Returns set of NFA states to which there is a transition on ast symbol
# +a+ from some state +s+ in +t+.
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
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.
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
def transitions
@table.map { |to, hash|
hash.map { |from, sym| [from, sym, to] }
}.flatten(1)
end
private
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
end
end
end
|
