Q2.What is the maximum number of reduce moves that can be taken by a bottom-up parser for a
grammar with no epsilon- and unit-production (i.e., of type A → ∈ and A → a) to parse a
string with n tokens?
Answer : Option BExplaination / Solution:
To have maximum number of reduce moves, all the productions will be of the typeA→αβ
(where α and β could be terminals or non-terminals). Consider the following illustration
then:
Answer : Option DExplaination / Solution:
There is an algorithm to check whether the given CFG is empty, finite or infinite and also to
convert NFA to DFA hence 1 and 4 are decidable
Q9.Which one of the following problems is undecidable?
Answer : Option AExplaination / Solution:
There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness
of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG,
so it is undecidable.
Consider the following languages over the alphabet Σ = {0,1,c}
Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree
languages?
Answer : Option CExplaination / Solution:
For the languages L1 and L2 we can have deterministic push down automata, so they are
DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a
deterministic CFL.
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0