Compilers

Context Free Grammar

Question 1
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 2
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 3
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 4
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 5
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 6
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 7
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 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%
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 10
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.