Class: Automata::NFA

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

Overview

Nondeterministic Finite Automata.

Direct Known Subclasses

PDA

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

#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.



96
97
98
 
# File 'lib/automata/nfa.rb', line 96

def accept_state?(state)
  @accept.include? state
end

#accepts?(input) ⇒ Boolean

Determines whether the NFA accepts a given string.

Parameters:

  • input (String) —

    the string to use as input for the NFA.

Returns:

  • (Boolean) —

    Whether or not the NFA accepts the input string.



62
63
64
65
 
# File 'lib/automata/nfa.rb', line 62

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 NFA

Returns:

  • (Hash) —

    a hash describing the NFA state after running

    • :input [String] the original input string

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

    • :heads [Array] the state which the head is currently on



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/automata/nfa.rb', line 16

def feed(input)
  heads = [@start]
  
  # Move any initial e-transitions
  if has_transition?(@start, '&')
    transition(@start, '&').each { |h| heads << h } 
  end
  
  # Iterate through each symbol of input string
  input.each_char do |symbol|
    newHeads, eTrans = [], []
            
    heads.each do |head|
      # Check if head can transition read symbol
      # Head dies if no transition for symbol
      if has_transition?(head, symbol)
        transition(head, symbol).each { |t| newHeads << t }
      end
    end
    
    # Move any e-transitions
    newHeads.each do |head|
      if has_transition?(head, '&')
        transition(head, '&').each { |t| eTrans << t }
      end
    end
    eTrans.each { |t| newHeads << t }
    
    heads = newHeads
    break if heads.empty?
  end
  
  accept = false
  heads.each { |head| accept = true if accept_state? head }

  resp = {
    input: input,
    accept: accept,
    heads: heads
  }
end

#has_transition?(state, symbol) ⇒ Boolean

Determines whether or not any transition states exist given a beginning state and input symbol pair.

Parameters:

  • state (String) —

    state label for beginning state.

  • symbol (String) —

    input symbol.

Returns:

  • (Boolean) —

    Whether or not a transition exists.



87
88
89
90
 
# File 'lib/automata/nfa.rb', line 87

def has_transition?(state, symbol)
  return false unless @transitions.include? state
  @transitions[state].has_key? symbol
end

#transition(state, symbol) ⇒ Array

Note:

NFA ε-transitions ε-transitions are supported through the use of the reserved input alphabet character ‘&’.

Determines the transition states, if any, from a given beginning state and input symbol pair.

Parameters:

  • state (String) —

    state label for beginning state.

  • symbol (String) —

    input symbol.

Returns:

  • (Array) —

    Array of destination transition states.



76
77
78
79
80
 
# File 'lib/automata/nfa.rb', line 76

def transition(state, symbol)
  dests = @transitions[state][symbol]
  dests = [dests] unless dests.kind_of? Array
  dests
end