Description
1 General Description
In this assignment you are expected to simulate a Push Down Automata (PDA).
Note that your simulation should work for any situation.
Your program should be working exactly as a PDA would do. Given a string the
simulated PDA should be able to tell if the string is accepted or rejected. Your
program should output the information about the given string being accepted
or rejected as well as which states it visited.
The programming languages allowed for this assignment are Java and C++.
For this assignment we first expect you to prepare a design for PDA simulation
within a week. Later you will be implementing your simulation according to
your design. The given time will be two weeks for the implementation part.
Also you will be submitting the final form of your design documents again while
you are submitting your implementation.
Please keep in mind that we are looking for a complex design. We expect you
to have a detailed structure (Multiple classes).
You will have a Demo for the assignment. In the Demo, you will need to
showcase that your program works as it supposed to. Also you should prove
that you implemented your work according to your design.
2 Example input and output files
Note that you are free to construct your own input file, it is fine as long as
your program works as it supposed to. Our goal here is to give you a brief
understanding of how to construct an input file.
1 CS 410
An input file should contain the stack alphabet, the starting symbol of the stack,
the input alphabet, number of states, the start state and the goal state(s). Once
those inputs are given you should express the state diagram that you want to
simulate. Finally, the string to detect could be given as an input. An example
file could be constructed as follows.
2.1 Input file
2 (number of variables in input alphabet)
2 (number of variables in stack alphabet)
2 (number of goal states)
4 (number of states)
q1 q2 q3 q4 (states)
q1 (start state)
q1 q4 (goal state(s))
X Y (the stack alphabet)
X (initial stack symbol)
0 1 (the input alphabet )
q1 ε ε X q2 (q1 state’inden ε ile q2 state’ine gidiyor, ε popluyor, X pushluyor.)
q2 0 ε Y q2 (q2 state’inden 0 ile q2 state’ine gidiyor, ε popluyor, Y pushluyor.)
q2 1 Y ε q3 (q2 state’inden 1 ile q3 state’ine gidiyor, Y popluyor, ε pushluyor.)
q3 1 Y ε q3 (q3 state’inden 1 ile q3 state’ine gidiyor, Y popluyor, ε pushluyor.)
q3 ε X ε q4 (q3 state’inden ε ile q4 state’ine gidiyor, X popluyor, ε pushluyor.)
0011 (string to be detected)
0111 (string to be detected)
An output file should contain information about whether the string is accepted
or rejected, as well as the path string followed. An example output file could
be constructed as follows:
2.2 Output file
q1 q2 q2 q2 q3 q3 q4 (route taken)
Accepted
q1 q2 q2 q3 (route taken)
Rejected
3 Submission and Grading criteria
You will be submitting both your implementation and design through LMS.
Design Grade: 30
Implementation Grade: 70
2 CS 410
