Compilers

Context Free Grammar

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The context free grammar S → A111|S1, A → A0 | 00 is equivalent to _________
{0n1m | n=2, m=3}
{0n1m | n=1, m=5}
{0n1m | n should be greater than two and m should be greater than four}
None of the mentioned
Explanation:
S-> A111
Question 2
Marks : +2 | -2
Pass Ratio : 100%
The context free grammar S → SS | 0S1 | 1S0 | ɛ generates _________
Equal number of 0’s and 1’s
Unequal number of 0’s and 1’s
Number of 0’s followed by any number of 1’s
None of the mentioned
Explanation:
S->SS
Question 3
Marks : +2 | -2
Pass Ratio : 100%
Which of the following statement is false?
The CFG can be converted to Chomsky normal form
The CFG can be converted to Greibach normal form
CFG is accepted by pushdown automata
None of the mentioned
Explanation:
All the statements follow the rules.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
Grammar that produce more than one Parse tree for same sentence is ___________
Ambiguous
Unambiguous
Complementation
Concatenation Intersection
Explanation:
An ambiguous grammar is one for which there is more than one parse tree for a single sentence.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
Grammars that can be translated to DFAs is ___________
Left linear grammar
Right linear grammar
Generic grammar
All of the mentioned
Explanation:
Right linear grammar can be translated to the DFAs.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
Assume the statements S1 and S2 given as:
S1 is correct and S2 is not correct
Both S1 and S2 are correct
Both S1 and S2 are not correct
S1 is not correct and S2 is correct
Explanation:
The proof of S1 can be seen in various book of theory of computation but s2 is a problem of category undecidable so a contradiction to this assumption can be easily obtained.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
Recursively enumerable languages are not closed under ______________
Union
Intersection
Complementation
Concatenation
Explanation:
Recursive languages are closed under the following operations.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
Which of the following conversion is not possible (algorithmically)?
Regular grammar to CFG
NDFA to DFA
NDPDA to DPDA
NDTM to DTM
Explanation:
Not every NDPDA has an equivalent deterministic PDA.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
A regular Grammar is a _________
CFG
Non CFG
English Grammar
None of the mentioned
Explanation:
Regular grammar is CFG. It restricts its rules to a single non terminal on left hand side.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
Automaton accepting the regular expression of any number of a’ s is ___________
a*
ab*
(a/b)*
a*b*c
Explanation:
It gives any number of a’s.