Class: Automata::PDA

Inherits:
NFA show all
Defined in:
lib/automata/pda.rb

Overview

Push Down Automata

Instance Attribute Summary collapse

Attributes inherited from StateDiagram

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

Instance Method Summary collapse

Constructor Details

#initialize(params = {}) ⇒ PDA

Initialize a PDA object.



7
8
9
10
11
 
# File 'lib/automata/pda.rb', line 7

def initialize(params={})
  super(params)
  @alphabet << '&' unless !@alphabet || @alphabet.include?('&')
  @stack = []
end

Instance Attribute Details

#stack ⇒ Object

Returns the value of attribute stack.



4
5
6
 
# File 'lib/automata/pda.rb', line 4

def stack
  @stack
end

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.



150
151
152
 
# File 'lib/automata/pda.rb', line 150

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

#accepts?(input) ⇒ Boolean

Determines whether the PDA accepts a given string.

This method is intended to override the parent accepts method.

Parameters:

  • input (String) —

    the string to use as input for PDA.

Returns:

  • (Boolean) —

    whether or not the PDA accepts the string.



79
80
81
82
 
# File 'lib/automata/pda.rb', line 79

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 PDA

Returns:

  • (Hash) —

    a hash describing the PDA state after running

    • :input [String] the original input string

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

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



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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/automata/pda.rb', line 21

def feed(input)
  heads, @stack, accept = [@start], [], false
  
  # Move any initial e-transitions
  eTrans = transition(@start, '&') if has_transition?(@start, '&')
  heads += eTrans

  puts "initial heads: #{heads}"
  puts "initial stack: #{@stack}"

  # Iterate through each symbol of input string
  input.each_char do |symbol|
    newHeads = []
    
    puts "Reading symbol: #{symbol}"

    heads.each do |head|
      puts "At head #{head}"

      # Check if head can transition read symbol
      # Head dies if no transition for symbol
      if has_transition?(head, symbol)
        puts "Head #{head} transitions #{symbol}"
        puts "stack: #{@stack}"
        transition(head, symbol).each { |t| newHeads << t }
        puts "heads: #{newHeads}"
        puts "stack: #{@stack}"
      end

    end
    
    heads = newHeads
    break if heads.empty?
  end

  puts "Loop finished"
  
  accept = includes_accept_state? heads

  puts "heads: #{heads}"
  puts "stack: #{stack}"
  puts "accept: #{accept}"

  resp = {
    input: input,
    accept: accept,
    heads: heads,
    stack: stack
  }
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.



135
136
137
138
139
140
141
142
143
144
 
# File 'lib/automata/pda.rb', line 135

def has_transition?(state, symbol)
  return false unless @transitions.has_key? state
  if @transitions[state].has_key? symbol
    actions = @transitions[state][symbol]
    return false if actions['pop'] && @stack.last != actions['pop']
    return true
  else
    return false
  end
end

#includes_accept_state?(states) ⇒ Boolean

Returns:

  • (Boolean) 


154
155
156
157
 
# File 'lib/automata/pda.rb', line 154

def includes_accept_state?(states)
  states.each { |s| return true if accept_state? s }
  return false
end

#pop?(symbol) ⇒ Boolean

Returns:

  • (Boolean) 


126
127
128
 
# File 'lib/automata/pda.rb', line 126

def pop?(symbol)
  @stack.last == symbol
end

#transition(state, symbol, stackTop = nil) ⇒ Array

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.



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/automata/pda.rb', line 90

def transition(state, symbol, stackTop=nil)
  dests = []

  if has_transition?(state, symbol)
    actions = @transitions[state][symbol]
    stackTop ||= @stack.last
    able = true
    @stack.push actions['push'] if actions['push']
    if actions['pop']
      able = false unless stackTop == actions['pop']
      @stack.pop if able
    end
    if able
      dests << actions['to']

      if has_transition?(actions['to'], '&')
        actions = @transitions[actions['to']]['&']
        able = true
        @stack.push actions['push'] if actions['push']
        if actions['pop']
          able = false unless @stack.last == actions['pop']
          @stack.pop if able
        end
        if able
          dests << actions['to']
        end
      end
      dests
    else
      return dests
    end
  else
    return []
  end
end