Class: Automata::DFA

Inherits:
StateDiagram show all
Defined in:
lib/automata/dfa.rb

Overview

Deterministic Finite Automata.

Instance Attribute Summary

Attributes inherited from StateDiagram

#accept, #alphabet, #start, #states, #transitions

Instance Method Summary collapse

Methods inherited from StateDiagram

#initialize

Constructor Details

This class inherits a constructor from Automata::StateDiagram

Instance Method Details

#accepts?(input) ⇒ Boolean

Determines whether the DFA accepts a given string.

Parameters:

  • input (String) —

    the string to use as input for the DFA.

Returns:

  • (Boolean) —

    whether or not the DFA accepts the string.



45
46
47
48
 
# File 'lib/automata/dfa.rb', line 45

def accepts?(input)
  resp = feed(input)
  resp[:accept]
end

#feed(input) ⇒ Hash

Runs the input on the machine and returns a Hash describing the machine’s final state after running.

Parameters:

  • input (String) —

    the string to use as input for the DFA

Returns:

  • (Hash) —

    a hash describing the DFA state after running

    • :input [String] the original input string

    • :accept [Boolean] whether or not the DFA accepted the string

    • :head [String] the state which the head is currently on



29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/automata/dfa.rb', line 29

def feed(input)
  head = @start.to_s
  input.each_char { |symbol| head = @transitions[head][symbol] }
  accept = is_accept_state? head
  resp = {
    input: input,
    accept: accept,
    head: head 
  }
  resp
end

#is_accept_state?(state) ⇒ Boolean

Determines if a given state is an accept state.

Parameters:

  • state (String) —

    the state label to check.

Returns:

  • (Boolean) —

    whether or not the state is an accept state.



54
55
56
 
# File 'lib/automata/dfa.rb', line 54

def is_accept_state?(state)
  @accept.include? state.to_s
end

#valid? ⇒ Boolean

Verifies that the initialized DFA is valid. Checks that each state has a transition for each symbol in the alphabet.

Returns:

  • (Boolean) —

    whether or not the DFA is valid.



9
10
11
12
13
14
15
16
17
18
19
 
# File 'lib/automata/dfa.rb', line 9

def valid?
  # @todo Check that each state is connected.
  #   Iterate through each states to verify the graph
  #   is not disjoint.
  @transitions.each do |key, val|
    @alphabet.each do |a| 
      return false unless @transitions[key].has_key? a.to_s
    end
  end
  return true
end