Skip to content

Latest commit

 

History

History
165 lines (125 loc) · 5.21 KB

README.md

File metadata and controls

165 lines (125 loc) · 5.21 KB

Exotic Project

Reversible PDA Validator and Simulator

By Steven Conaway and Anna Teerlinck

This project is a Reversible PDA Validator and Simulator developed as part of CSE 40932: Exotic Computing.

Table of Contents

  1. Introduction
  2. Usage
  3. Formal Automaton Description
  4. Examples

Introduction

This project explores a Reversible Pushdown Automaton (R-PDA), a computational model combining a stack-based automaton with reversibility. The validator checks for machine reversibility, while the simulator executes both forward and backward simulations of a PDA.

Usage

Run the program using:

$ python3 rePDAsim.py machine.pda [input_string direction (f|b)]

Parameters

  1. machine.pda (required): A file containing the PDA transitions in CSV format.

    • Example: 
      direction,fromState,inputChar,stackChar,toState,stackChange
f,q0,ep,ep,q1,$
f,q1,(,ep,q1,(
f,q1,),(,q1,ep
f,q1,ep,$,qacc,ep
      • ep represents an empty string ($\epsilon$ in formal notation).

  2. input_string (optional): The string for the PDA to process.

    • If omitted, the program will run in interactive mode

  3. direction (optional): Specifies the simulation direction.

    • f for forward, b for backward.

Examples

Automated Mode

Run the simulator with an input string and direction:

$ python3 rePDAsim.py examples/counting.pda "(()())" f
current_state: q0, char: (, direction: f, stack: []
current_state: q1, char: (, direction: f, stack: ['$']
current_state: q1, char: (, direction: f, stack: ['$', '(']
current_state: q1, char: ), direction: f, stack: ['$', '(', '(']
current_state: q1, char: (, direction: f, stack: ['$', '(']
current_state: q1, char: ), direction: f, stack: ['$', '(', '(']
current_state: q1, char: ), direction: f, stack: ['$', '(']
current_state: q1, char: , direction: f, stack: ['$']
Simulation results:
	Final state: qacc
	Stack content: []
	Accept state reached: True
$ python3 rePDAsim.py examples/counting.pda "(()())" b
current_state: qacc, char: ), direction: b, stack: []
current_state: q1, char: ), direction: b, stack: ['$']
current_state: q1, char: ), direction: b, stack: ['$', '(']
current_state: q1, char: (, direction: b, stack: ['$', '(', '(']
current_state: q1, char: ), direction: b, stack: ['$', '(']
current_state: q1, char: (, direction: b, stack: ['$', '(', '(']
current_state: q1, char: (, direction: b, stack: ['$', '(']
current_state: q1, char: , direction: b, stack: ['$']
Simulation results:
	Final state: q0
	Stack content: []
	Accept state reached: True

Interactive Mode

Run the validator without simulating:

$ python3 rePDAsim.py examples/counting.pda
Enter characters and direction {'f' or 'b'} (e.g., '0f', '1b').
Type 'exit' to quit.
Input: (f
current_state: q0, char: (, direction: f, stack: []
State: q1, Stack: ['$'], input not consumed
Input: (f
current_state: q1, char: (, direction: f, stack: ['$']
State: q1, Stack: ['$', '(']
Input: (f
current_state: q1, char: (, direction: f, stack: ['$', '(']
State: q1, Stack: ['$', '(', '(']
Input: )f
current_state: q1, char: ), direction: f, stack: ['$', '(', '(']
State: q1, Stack: ['$', '(']
Input: (f
current_state: q1, char: (, direction: f, stack: ['$', '(']
State: q1, Stack: ['$', '(', '(']
Input: )f
current_state: q1, char: ), direction: f, stack: ['$', '(', '(']
State: q1, Stack: ['$', '(']
Input: )f
current_state: q1, char: ), direction: f, stack: ['$', '(']
State: q1, Stack: ['$']
Input:
assuming no input character, forward
current_state: q1, char: , direction: f, stack: ['$']
State: qacc, Stack: []
Accept state reached.

Formal Automaton Description

A Bidirectional Pushdown Automaton (BPDA) extends a PDA to support reversible computations. Key features include:

  1. Control Input:

    • Control symbols $f$ and $b$ specify forward and backward directions, respectively.

  2. Stack Operations:

    • Operations include push, pop, and no-op, defined for each transition.

  3. Transition Function:

    • $\delta: Q \times \Sigma \times \Gamma \times \beta \to Q \times \Gamma^*$
    • Example:
      • Forward: $\delta(q_0, a, Z, f) = (q_1, \gamma)$
      • Reverse: $\delta^{-1}(q_1, a, \gamma, b) = (q_0, Z)$

  4. Reversibility:

    • For every forward transition, there exists an inverse transition. Specifically, for every $\delta(q, a, Z, c) = (q', \gamma, d)$ (where $q$ is the current state, $a$ the tape character, $Z$ the stack's top, $c$ the control input, and $\gamma$ the new stack string), there exists a corresponding transition $\delta^{-1}(q', a', \gamma', c') = (q, Z, d')$ such that the automaton can backtrack.

Notes

  • The ep symbol:
    • Represents "no character" (input character or top of stack) or "no stack change."
    • Used for empty string transitions and no-op stack changes.
  • Non-reversible simulation:
    • Machines do not need to be reversible to simulate them. However, the reversibility check will fail for such machines.
  • Limitations:
    • A stack or input character which is a space character will be treated as an empty string.