PDA Implementation
class PushdownAutomaton:
def __init__(self, states, input_alphabet, stack_alphabet,
transitions, start_state, start_stack, final_states):
self.states = states
self.input_alphabet = input_alphabet
self.stack_alphabet = stack_alphabet
self.transitions = transitions
self.start_state = start_state
self.start_stack = start_stack
self.final_states = final_states
def process_string(self, input_string):
stack = [self.start_stack]
current_state = self.start_state
position = 0
trace = []
while position <= len(input_string):
if position == len(input_string):
symbol = 'ε' # End of input
else:
symbol = input_string[position]
stack_top = stack[-1] if stack else None
transition_key = (current_state, symbol, stack_top)
if transition_key in self.transitions:
next_state, stack_ops = self.transitions[transition_key]
# Apply stack operations
if stack_ops == 'pop':
stack.pop()
elif stack_ops.startswith('push_'):
stack.append(stack_ops[5:])
trace.append(@{
'state': current_state,
'input': symbol,
'stack_before': stack[:],
'stack_after': stack[:],
'next_state': next_state
@})
current_state = next_state
if symbol != 'ε':
position += 1
else:
break
accepted = (current_state in self.final_states and
len(stack) == 1 and stack[0] == self.start_stack)
return accepted, trace
# Example PDA for @{a^n b^n | n >= 1@}
pda = PushdownAutomaton(
states=@{'q0', 'q1', 'q2', 'q3'@},
input_alphabet=@{'a', 'b'@},
stack_alphabet=@{'A', 'Z0'@},
transitions=@{
('q0', 'a', 'Z0'): ('q1', 'push_A'),
('q1', 'a', 'A'): ('q1', 'push_A'),
('q1', 'b', 'A'): ('q2', 'pop'),
('q2', 'b', 'A'): ('q2', 'pop'),
('q2', 'ε', 'Z0'): ('q3', '')
@},
start_state='q0',
start_stack='Z0',
final_states=@{'q3'@}
)