DFA and NFA

fa.rb

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

note.markdown

NFA 增加了三个不确定性：

1. 对未知输入的处理：某个状态下对于某些输入没有转换规则。
2. 对已知输入的不确定处理：某个状态下对于某个输入有多个转换规则。
3. 自身状态变化的不确定性：某个状态下可以进行空转换。