NFA 增加了三个不确定性:
- 对未知输入的处理:某个状态下对于某些输入没有转换规则。
- 对已知输入的不确定处理:某个状态下对于某个输入有多个转换规则。
- 自身状态变化的不确定性:某个状态下可以进行空转换。
require 'set' | |
### finite automata rule | |
class FARule < Struct.new(:state, :character, :next_state) | |
def applies_to?(state, character) | |
self.state = state && self.character == character | |
end | |
def follow | |
next_state | |
end | |
def inspect | |
"#<FARule #{state.inspect} --#{character}--> #{next_state.inspect}" | |
end | |
end | |
### DFA rules | |
class DFARuleBook < Struct.new(:rules) | |
def next_state(state, character) | |
rule_for(state, character).follow | |
end | |
private | |
def rule_for(state, character) | |
rules.find { |rule| rule.applies_to?(state, character) } | |
end | |
end | |
### DFA | |
class DFA < Struct.new(:current_state, :accept_states, :rulebook) | |
def accepting? | |
accept_states.include?(current_state) | |
end | |
end | |
### monkey patching, add input-reading methods | |
class DFA | |
def read_character(character) | |
self.current_state = rulebook.next_state(current_state, character) | |
end | |
def read_string(string) | |
string.chars.each do |character| | |
read_character(character) | |
end | |
end | |
end | |
### DFA template | |
class DFADesign < Struct.new(:start_state, :accept_states, :rulebook) | |
def accepting?(string) | |
to_dfa.tap { |nfa| nfa.read_string(string) }.accepting? | |
end | |
private | |
def to_dfa | |
DFA.new(start_state, accept_states, rulebook) | |
end | |
end | |
### NFA rules | |
class NFARuleBook < Struct.new(:rules) | |
def next_states(states, character) | |
states.flat_map { |state| follow_rules_for(state, character) }.to_set | |
end | |
private | |
def follow_rules_for(state, character) | |
rules_for(state, character).map(&:follow) | |
end | |
def rules_for(state, character) | |
rules.select { |rule| rule.applies_to?(state, character) } | |
end | |
end | |
### NDA | |
class NFA < Struct.new(:current_states, :accept_states, :rulebook) | |
def accepting? | |
(current_states & accept_states).any? | |
end | |
end | |
### monkey patching, add input-reading methods | |
class NFA | |
def read_character(character) | |
self.current_states = rulebook.next_states(current_states, character) | |
end | |
def read_string(string) | |
string.chars.each do |character| | |
read_character(character) | |
end | |
end | |
end | |
### NFA template | |
class NFADesign < Struct.new(:start_state, :accept_states, :rulebook) | |
def accepting?(string) | |
to_nfa.tap { |nfa| nfa.read_string(string) }.accepting? | |
end | |
private | |
def to_nfa | |
NFA.new(Set.new([start_state]), accept_states, rulebook) | |
end | |
end | |
### add free moves support | |
class NFARuleBook | |
def follow_free_moves(states) | |
more_states = next_states(states, nil) | |
if more_states.subset?(state) | |
states | |
else | |
follow_free_moves(states + more_states) | |
end | |
end | |
end | |
class NFA | |
def current_states | |
rulebook.follow_free_moves(super) | |
end | |
end |
NFA 增加了三个不确定性: