CS 341 Fall 2023
Instructor: Ravi Varadarajan
DPDA simulator and design
Project Goal
The goal of this project is to implement a deterministic PDA simulator that can
simulate the actions of any DPDA given as input in order to determine if an input
string is accepted by the DPDA or not. In addition, you will be designing a DPDA
for a given CFG and testing the DPDA design using the simulator.
You can choose to partner with one person to work on this project.
DPDA Definition
DPDA is generally specified as (?, Σ, Γ, ?, ?!, F) where Q is a finite set of states, Σ
is the input alphabet, Γ is the stack alphabet, ? : Q x (Σ ∪ {∈}) x (Γ ∪ {∈}) → Q x
Γ∗, ?! ? ? is the start state and F ⊆ ? is the set of accepting states. The transition
function value ?(q, x, t) = (r, w) specifies that given cu
ent state q, input symbol
ead = x (x can be ∈) and top of stack symbol = t (t can be ∈), the next state
will be r and the top of stack symbol replaced by the string w (w can be ∈).
Note we extended the standard definition of PDA so that more than one symbol
can be pushed to the stack. In the DPDA, the following must be satisfied for the
transition function ? for a given state q:
(a) if ?(q, ∈, ∈) exists (i.e. no input read, no popping of stack) then no other
transition of any kind must exist for the state q.
(b) if ?(q, ∈, ?) exists where ? is not ∈ ,(i.e. no input read, but top of stack
symbol ? ?? ????) then no other transition must exist for the state q
matching top of stack ? and any input symbol including ∈.
(c) if ?(q, ?, ∈) exists for an input symbol ? (i.e. input is read and no popping
of stack), then no other transition can exist for the state q matching input
symbol ? and any top of stack symbol including ∈.
(d) in all other cases, i.e. if ?(q, ?, ?) for an input symbol a and top of stack
symbol ? (where t is not ∈) exists then it must be unique for the state
matching input symbol ? and top of stack symbol ?.
? is a partial function meaning that if a transition from a state for an input symbol
(including ∈) and top of stack symbol (including ∈) is missing during processing
of a string, the DPDA crashes rejecting the string.
Keshav Patel
Keshav Patel
Keshav Patel
Part 1 : DPDA simulator
We only need to specify the number of states, input alphabet, accepting states and
the transition function. We do not need to specify the stack alphabet or the start
state. Given n states ?!,?$,, . . ?%&$ the start state is assumed to be ?!. When a new
transition rule is entered, it needs to be checked against the existing transitions to
verify if it does not violate the properties of DPDA . DO NOT wait to check this
until after the user enters all the transitions for the state or for the DPDA. A sample
user interactive session for the DPDA simulator for entering a DPDA specification
for the CFL 0%1% is given as follows (user input shown in bold). This session also
shows how invalid inputs are checked immediately so that the user can reenter the
valid inputs.
Enter number of states :
4
Enter input alphabet as a comma-separated list of symbols :
0,1
Enter accepting states as a comma-separated list of integers :
4
invalid state 4; enter a value between 0 and 3
checking for valid state number
Enter accepting states as a comma-separated list of integers :
3
Transitions for state 0:
Need a transition rule for state 0 ? (y or n)y
Input Symbol to read (enter - for epsilon): -
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 1
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): $
Transitions for state 0:
[eps,eps->$]
Need a transition rule for state 0 ? (y or n)y
Input Symbol to read (enter - for epsilon): 0
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): 0
Violation of DPDA due to epsilon input/epsilon stack transition from state
0:[eps,eps->$]
violation of property (a) and (c) of DPDA
Transitions for state 0:
[eps,eps->$]
Need a transition rule for state 0 ? (y or n)y
Input Symbol to read (enter - for epsilon): -
Stack symbol to match and pop (enter - for epsilon): 0
State to transition to : 3
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to epsilon input/epsilon stack transition from state
0:[eps,eps->$]
violation of property (a) and (b) of DPDA
Transitions for state 0:
[eps,eps->$]
Need a transition rule for state 0 ? (y or n)y
Input Symbol to read (enter - for epsilon): 0
Stack symbol to match and pop (enter - for epsilon): 0
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to epsilon input/epsilon stack transition from state
0:[eps,eps->$]
violation of property (a) and (d) of DPDA
Transitions for state 0:
[eps,eps->$]
Need a transition rule for state 0 ? (y or n)y
Input Symbol to read (enter - for epsilon): -
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to epsilon input/epsilon stack transition from state
0:[eps,eps->$]
violation of property (a) of DPDA
Transitions for state 0:
[eps,eps->$]
Need a transition rule for state 0 ? (y or n)n
Transitions for state 1:
Need a transition rule for state 1 ? (y or n)y
Input Symbol to read (enter - for epsilon): 0
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 1
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): 0
Transitions for state 1:
[0,eps->0]
Need a transition rule for state 1 ? (y or n)y
Input Symbol to read (enter - for epsilon): 1
Stack symbol to match and pop (enter - for epsilon): 0
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Transitions for state 1:
[0,eps->0]
[1,0->eps]
Need a transition rule for state 1 ? (y or n)y
Input Symbol to read (enter - for epsilon): -
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to epsilon stack transition from state 1:[0,eps->0]
violation of property (a) and (c) of DPDA
Transitions for state 1:
[0,eps->0]
[1,0->eps]
Need a transition rule for state 1 ? (y or n)n
Transitions for state 2:
Need a transition rule for state 2 ? (y or n)y
Input Symbol to read (enter - for epsilon): 1
Stack symbol to match and pop (enter - for epsilon): 0
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Transitions for state 2:
[1,0->eps]
Need a transition rule for state 2 ? (y or n)y
Input Symbol to read (enter - for epsilon): 1
Stack symbol to match and pop (enter - for epsilon): -
State to transition to : 2
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to epsilon stack transition from state 2:[1,0->eps]
Transitions for state 2:
violation of property (a) and (c) and of DPDA
[1,0->eps]
Need a transition rule for state 2 ? (y or n)y
Input Symbol to read (enter - for epsilon): 1
Stack symbol to match and pop (enter - for epsilon): 0
State to transition to : 3
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Violation of DPDA due to multiple transitions for the same input and stack top
from state 2:[1,0->eps]
violation of property (d) of DPDA
Transitions for state 2:
[1,0->eps]
Need a transition rule for state 2 ? (y or n)y
Input Symbol to read (enter - for epsilon): -
Stack symbol to match and pop (enter - for epsilon): $
State to transition to : 3
Stack symbols to push as comma separated list, first symbol to top of stack (enter -
for epsilon): -
Transitions for state 2:
[1,0->eps]
[eps,$->eps]
Need a transition rule for state 2 ? (y or n)n
Transitions for state 3:
Need a transition rule for state 3 ? (y or n)n
Printing all transitions...
Transitions for state 0:
[eps,eps->$]
Transitions for state 1:
[0,eps->0]
[1,0->eps]
Transitions for state 2:
[1,0->eps]
[eps,$->eps]
Transitions for state 3:
After entering the DPDA specification, we can enter an input string to get the
sequence of configurations the DPDA goes through in processing the string and
verify if it is accepted or rejected by the DPDA. You should be able to do this for
any number of input strings. Note that a configuration is given as a triplet (q;w;x)
where q is the cu
ent state, w is the remaining input string to be read and x is the
stack contents, (from top to bottom). Also you need to show which transition rule
has been used on moving from once configuration to the next. A sample user
session for doing this is given below.
For example in the following output, (q1;000111;$)--[0,eps->0]-->(q1;00111;0$)
shows that when the remaining input string is XXXXXXXXXXin state q1, the transition rule
[0,eps->0] is applied and the input symbol 0 is pushed to the stack and it remains
in state q1.
Enter an input string to be processed by the PDA :
000111
Accept string 000111?true
(q0;000111;eps)--[eps,eps->$]-->(q1;000111;$)--[0,eps->0]-->(q1;00111;0$)--
[0,eps->0]-->(q1;0111;00$)--[0,eps->0]-->(q1;111;000$)
--[1,0->eps]-->(q2;11;00$)--[1,0->eps]-->(q2;1;0$)--[1,0->eps]-->(q2;eps;$)--
[eps,$->eps]-->(q3;eps;eps)
Enter an input string to be processed by the PDA :
00111
Accept string 00111?false
(q0;00111;eps)--[eps,eps->$]-->(q1;00111;$)--[0,eps->0]-->(q1;0111;0$)--
[0,eps->0]-->(q1;111;00$)--[1,0->eps]-->(q2;11;0$)
--[1,0->eps]-->(q2;1;$)--[eps,$->eps]-->(q3;1;eps)
Enter an input string to be processed by the PDA :
0000011
Accept string XXXXXXXXXX?false
(q0;0000011;eps)--[eps,eps->$]-->(q1;0000011;$)--[0,eps->0]--
(q1;000011;0$)--[0,eps->0]-->(q1;00011;00$)--[0,eps->0]-->(q1;0011;000$)
--[0,eps->0]-->(q1;011;0000$)--[0,eps->0]-->(q1;11;00000$)--[1,0->eps]--
(q2;1;0000$)--[1,0->eps]-->(q2;eps;000$)
Part 2 : DPDA design for the expression language
For the second part of the project, you need to design a DPDA for the following
unambiguous CFG for generating simple arithmetic expressions. You should then
use your simulator to check if it accepts only strings generated by the grammar.
It is given by G = (V, Σ, R, S), where V = {S, E, E1, T, T1, F}, Σ =
{0,1,2,3,4,5,6,7,8,9,+,-*,/,(,),$} and the set of production rules R is given as:
? → ?$
? → ? ??
?? → +? ?? | −? ?? | ∈
? → ? ??
?? → ∗ ? ?? | / ? ?? | ∈
? → (?) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
For example the string XXXXXXXXXX*3/2 can be generated using the following leftmost
derivation:
? ⇒ ?$ ⇒ ? ??$ ⇒ ? ?? ??$ ⇒ (?) ?? ??$ ⇒ (? ??) ?? ??$ ⇒ (? ?? ??) ?? ??$
⇒ (? ?? ??) ?? ??$ ⇒ (? ∈ ??) ?? ??$ ⇒ (? + ? ??) ?? ??$ ⇒ (? + ? ?? ??) ?? ??$
⇒ (? + ? ?? ??) ?? ??$ ⇒ (? + ? ∈ ??) ?? ??$ ⇒ (? + ? ∈) ?? ??$ ⇒ (? + ?) ∈ ??$
⇒ (? + ?)