Compilers

Context Free Grammar

Question 1
Marks : +2 | -2
Pass Ratio : 100%
Which of the following statement is false?
In derivation tree, the label of each leaf node is terminal
In derivation tree, the label of all nodes except leaf nodes is a variable
In derivation tree, if the root of a sub tree is X then it is called –tree
None of the mentioned
Explanation:
All of them are true regarding a derivation tree.
Question 2
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 3
Marks : +2 | -2
Pass Ratio : 100%
Which of the following language accepted by a Push down Automata?
Type0
Type1
Type2
Type3
Explanation:
A known fact that type 2 grammar is accepted by PDA.
Question 4
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 5
Marks : +2 | -2
Pass Ratio : 100%
Which of these does not belong to CFG?
Terminal Symbol
Non terminal Symbol
Start symbol
End Symbol
Explanation:
CFG consists of terminal non terminal start symbol set of production rules but does not have an end symbol.
Question 6
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 7
Marks : +2 | -2
Pass Ratio : 100%
Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?
I only
II only
Both I and II
Neither I nor II
Explanation:
Recursive languages are closed under the following operations.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
If P & R are regular and also given that if PQ=R, then?
Q has to be regular
Q cannot be regular
Q need not be regular
Q has to be a CFL
Explanation:
If two regular languages when combined do not always produce a regular language.
Question 9
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.
Question 10
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.