Automata on ruby

Question

I have the following Automata 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

Output:

True
False
False

The problem is that i want this Automata to be able to 'eat' 'ANY OTHER' symbol. It would be like 'default' or 'else' action. For example:

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

So, it will be possible to write:

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

and get 'True'. What are possible solutions? Thank you!

P.S. I have to write an Automata, which will be able to parse .INI files. May be it would be better not to write a class, but just to form my automata in 'case...when...when...else...' statement? What do you think?

Answer 1

You could define a special symbol:

class DFA
  ANY = :any

And calculate the state based on it:

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

And use it defining DFA:

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

Complete example after refactoring:

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