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:
- 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. - 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)
- 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. Bothdpda.txt
andinput.txt
should be assumed to be in the same directory as your Python program. Simulate each string ininput.txt
using your DPDA, and write the output (accept or reject) into a new file calledoutput.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.