Question Discussion & Solution

To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:

Which of the following statement is false?

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z₀, X} where Z₀ is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) ? (t, XZ₀) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z₀ and X (in that order) on the stack.
(s, a, Z₀) ? (s, XXZ₀)
(s, ?, Z₀) ? (f, ?)
(s, a, X) ? (s, XXX)
(s, b, X) ? (t, ?)
(t, b, X) ? (t,.?)
(t, c, X) ? (u, ?)
(u, c, X) ? (u, ?)
(u, ?, Z₀) ? (f, ?)
The language accepted by the PDA is

Consider the following context-free grammars:

Which one of the following pairs of languages is generated by G1 and G2, respectively

With reference of a DPDA, which among the following do we perform from the start state with an empty stack?