Project 5

Constructing a DPDA Simulator

Project Overview

This project will get you acquainted with deterministic pushdown automata (DPDAs). You will write a Python program that simulates a DPDA.

What you need to do

Before you begin coding, I highly recommend to read up on DPDAs (as they are just slightly different than PDAs). To do this, read the first part of Section 2.4 of your textbook (pages 130-131).

Write a Python program (call it dpda.py) by completing the following steps:

  1. In whichever approach you wish, have your program read in a text file called dpda.txt and construct a DPDA. This file will contain data that describes a DPDA.
  2. The structure of dpda.txt will be as follows:
    • Line 1: the states of the DPDA (separated by commas, if there is more than one state)
    • Line 2: the alphabet of the DPDA (separated by commas, if there is more than one symbol)
    • Line 3: the alphabet of the stack
    • Line 4: the starting state of the DPDA
    • Line 5: the final/accept states of the DPDA (separated by commas, if there is more than one accept state)
    • Line 6 and onward: the transition rules, where each rule takes the form a,b,c,d,e (where being in state ‘a’ and reading symbol ‘b’ while popping ‘c’ from the top of the stack transitions to new state ‘d’ and pushes ‘e’ on the top of the stack)
  3. In addition to the given alphabet, all DPDAs may also contain empty-string transitions for either the input character, the symbol at the top of the stack, or both (we will use ‘@’ to represent this). You can use any symbol for the bottom of the stack, but the provided examples I will give you use a ‘$’. After your program constructs a DPDA, read in another file called input.txt, where each line in the file is a string that will run on your DPDA. Both dpda.txt and input.txt should be assumed to be in the same directory as your Python program. Simulate each string in input.txt using your DPDA, and write the output (accept or reject) into a new file called output.txt (also in the same directory as your Python program, and each result on a new line).

How to submit

To submit, save your Python program in a file named dpda.py, and upload/submit it to Moodle by the due date.