Compilers

Context Free Grammar

Question 1
Marks : +2 | -2
Pass Ratio : 100%
A context free language is called ambiguous if _________
It has 2 or more left derivations for some terminal string Ñ¡ Ñ” L (G)
It has 2 or more right derivations for some terminal string Ñ¡ Ñ” L (G)
It has 2 or more left & right derivations for some terminal string Ñ¡ Ñ” L (G)
None of the mentioned
Explanation:
A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.
Question 2
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 3
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 4
Marks : +2 | -2
Pass Ratio : 100%
Consider the grammar given below E? E+E | E*E | E-E | E/E | E^E | (E) | id Assume that + and ^ have the same but least precedence, * and / have the next higher precedence but the same precedence and finally ^ has the highest precedence. Assume + and ^ associate to the left like * and / and that ^ associates to the right. Choose the correct for the ordered pairs (^,^), (-,-), (+,+), (*,*) in the operator precedence table constructed for the grammar.
All <
All >
< >, =
< > > >
Explanation:
This relation is established of basis of the precedence of operators.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
Push down automata accepts which language?
Context sensitive language
Context free language
Recursive language
None of the mentioned
Explanation:
PDA accepts CFG.
Question 6
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 7
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 8
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 9
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 10
Marks : +2 | -2
Pass Ratio : 100%
A CFG is closed under _________
Union
Kleene star
Concatenation
None of the mentioned
Explanation:
CFG is closed under the above mentioned 3 operations.