Theory of Computation
Q131.
Let L_1 be the set of all languages accepted by a PDA by final state and L_2 the set of all languages accepted by empty stack. Which of the following is true?Q132.
Consider the NPDA \langle Q=\{q_{0},q_{1},q_{2}\}, \Sigma =\{0,1\}, \Gamma =\{0,1,\perp \},\delta ,q_{0},\perp , F=\{q_{2}\} \rangle, where (as per usual convention) Q is the set of states, \Sigma is the input alphabet, \Gamma is the stack alphabet, \delta is the state transition function, q_{0} is the initial state, \perp is the initial stack symbol, and F is the set of accepting states. The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?Q133.
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?Q134.
Consider the transition diagram of a PDA given below with input alphabet \Sigma ={a,b} and stack alphabet \Gamma={X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?Q135.
Let M=(K, \Sigma, \Gamma, \Delta, s, F) be a pushdown automaton, where K=(s, f), F=\{f\}, \Sigma=\{a, b\}, \Gamma=\{a\} \text { and } \Delta=\{((s, a, \epsilon),(s, a)),((s, b, \epsilon),(s, a)),((s, a, a),(f, \epsilon)),((f, a, a),(f, \epsilon)) ((f, b, a),(f, \epsilon))\}Which one of the following strings is not a member of L(M)?Q136.
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be \Sigma. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?Q137.
Which of the following languages over \left\{a,b,c\right\} is accepted by a deterministic pushdown automata?Q138.
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet \{a,b\}, has stack alphabet \{ \perp ,A\}, and has three states \{s,p,q\}, with s being the start state. A transition from state u to state v , labelled c/X/\gamma , where c is an input symbol or , X is a stack symbol, and \gamma is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string \gamma on the stack, and go to state v. In the initial configuration, the stack has only the symbol \perp in it. The PDA accepts by empty stack.Which one of the following options correctly describes the language accepted by P?