pdf attached
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 current state q, input symbol read = x (x can be ∈)andtopofstacksymbol = t(tcanbe ∈),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 current 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 000111 in 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 0000011?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 (2+5)-4*3/2 can be generated using the following leftmost derivation: ? ⇒ ?$ ⇒ ? ??$ ⇒ ? ????$ ⇒ (?) ????$ ⇒ (???) ????$ ⇒(?????) ????$ ⇒ (?????) ????$ ⇒(? ∈ ??) ????$ ⇒(? + ???) ????$ ⇒(? + ?????) ????$ ⇒ (? + ?????) ????$ ⇒(? + ? ∈ ??) ????$ ⇒(? + ? ∈) ????$ ⇒ (? + ?) ∈ ??$ ⇒ (? + ?)