1. Consider the following PDA with input alphabet -ta,b,#1 b,a-> E 4i q2 23 Please answer the following questions. (a) Consider the following list of stack configurations (i) Provide an input string such that based on each of these strings, the PDA has its stack updated as in the list of stack configurations above Sa Saa 0 Sa (ii) Provide the list of states visited for recognising this word Sa (iii) Is it possible for this PDA to provide a list of stack configurations (like Saa Sa the one above) such that one could provide two different accepted input strings corresponding to these updates? If yes, provide such an example otherwise, state no (b) Please describe the language of the PDA above using (i) set notation, and (ii) using a context-free grammar (c) A deterministic PDA is a PDA which has no nondeterministic decisions This means that (i) In each state q (except the accepting state), either A. there is a single transition , u u, but no other transitions, or B. for each tuple (q, c, t) of q, character from the input alphabet cE and character (or E) from the stack alphabet t E I. U {c) there is at most one transition Also, if there is a transition (g,c, E), then no further transition (g, e, t) is allowed for the according state q and input (for any t { Provide a deterministic PDA which recognises the same language as the PDA above Note: Added clarification above The basic idea is that there is no choice in what the automaton is supposed next, because in each situation either there is only one e transition such that the automaton has to execute this transition, or there is a single (q, ce) transition for the current state q and input character c, or there is a single (g, c,t) transition for the current state q, input character c and top stack character t 1. Consider the following PDA with input alphabet -ta,b,#1 b,a-> E 4i q2 23 Please answer the following questions. (a) Consider the following list of stack configurations (i) Provide an input string such that based on each of these strings, the PDA has its stack updated as in the list of stack configurations above Sa Saa 0 Sa (ii) Provide the list of states visited for recognising this word Sa (iii) Is it possible for this PDA to provide a list of stack configurations (like Saa Sa the one above) such that one could provide two different accepted input strings corresponding to these updates? If yes, provide such an example otherwise, state no (b) Please describe the language of the PDA above using (i) set notation, and (ii) using a context-free grammar (c) A deterministic PDA is a PDA which has no nondeterministic decisions This means that (i) In each state q (except the accepting state), either A. there is a single transition , u u, but no other transitions, or B. for each tuple (q, c, t) of q, character from the input alphabet cE and character (or E) from the stack alphabet t E I. U {c) there is at most one transition Also, if there is a transition (g,c, E), then no further transition (g, e, t) is allowed for the according state q and input (for any t { Provide a deterministic PDA which recognises the same language as the PDA above Note: Added clarification above The basic idea is that there is no choice in what the automaton is supposed next, because in each situation either there is only one e transition such that the automaton has to execute this transition, or there is a single (q, ce) transition for the current state q and input character c, or there is a single (g, c,t) transition for the current state q, input character c and top stack character t
