自动机是 ruby

Question

我有以下自动机class：

class DFA
  attr_accessor :start, :end, :transition

  def initialize(options = {})
    @start = options[:start]
    @end = options[:end]
    @transition = options[:transition]
  end

  def run(input)
    current_state = @start
    for i in input
      current_state = @transition[current_state][i]
    end
    return true if @end.include? current_state
    return false
  end
end

if $PROGRAM_NAME == __FILE__
  d = DFA.new(:start => :q1, :end => [:q2],
              :transition =>
              { :q1 => {'0' => :q1, '1' => :q2},
                :q2 => {'0' => :q3, '1' => :q2},
                :q3 => {'0' => :q2, '1' => :q3}
              })

  puts d.run(['1','1','0','0'])
  puts d.run(['1','1','0','0','0'])
  puts d.run(['0','0','0'])
end

输出：

True
False
False

问题是我希望这个自动机能够 'eat' 'ANY OTHER' 符号。这就像 'default' 或 'else' 操作。例如：

{ :q1 => {'0' => :q1, 'ANY OTHER SYMBOL' => :q2},

所以，可以这样写：

    puts d.run(['1','1','0','a'])

得到'True'。有哪些可能的解决方案？谢谢！

P.S。我必须编写一个 Automata，它将能够解析 .INI 文件。可能最好不要写 class，而只是在 'case...when...when...else...' 语句中形成我的自动机？你怎么看？

Answer 1

您可以定义一个特殊符号：

class DFA
  ANY = :any

并据此计算状态：

state = @transitions[state][step] || @transitions[state][DFA::ANY]

并使用它定义 DFA：

{'0' => :q1, '1' => :q2, DFA::ANY => :q2}

重构后的完整示例：

class DFA
  ANY = :any

  attr_accessor :start, :end, :transitions

  def initialize(options = {})
    @start = options[:start]
    @end = options[:end]
    @transitions = options[:transitions]
  end

  def run(steps)
    state = @start

    steps.each do |step|
      state = @transitions[state][step] || @transitions[state][DFA::ANY]
      raise 'Unexpected Symbol' if state.nil?
    end

    @end.include? state
  end
end

dfa = DFA.new start: :q1,
              end: [:q2],
              transitions: {
                q1: {'0' => :q1, '1' => :q2, DFA::ANY => :q2},
                q2: {'0' => :q3, '1' => :q2},
                q3: {'0' => :q2, '1' => :q3}
              }

puts dfa.run(['Q', '0', '0']) #=> true

自动机是 ruby

Automata on ruby

ruby

automata