-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfa.rb
42 lines (30 loc) · 1.05 KB
/
dfa.rb
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
State = Struct.new(:name, :is_start, :is_accept)
class DFA
attr_reader :states, :initial_state, :transition_hash
def initialize(states, transition_hash)
@states = states
@initial_state = states.select{|s| s.is_start}.first
@transition_hash = transition_hash
end
def accept_states
@states.select{|s| s.is_accept}
end
def compute_final_state(string)
string.split("").inject(@initial_state) {|state, ch| compute_next_state(state, ch)}
end
def accepts?(string)
compute_final_state(string).is_accept
end
private
def get_state_by_name(name)
raise "State with name #{name} could not be found" unless state = @states.select{|s| s.name == name}.first
state
end
def compute_next_state(current_state, character)
if next_state_name = @transition_hash[current_state.name] && @transition_hash[current_state.name][character]
get_state_by_name next_state_name
else
raise "Could not calculate the next state's name with inputs -- state: #{current_state} and character: #{character}"
end
end
end