Compilers

Context Free Grammar

Question 1
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 2
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 3
Marks : +2 | -2
Pass Ratio : 100%
Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?
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 assumptions of statement S1 and S2 are correct.
Question 4
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 5
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 6
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 7
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.
Question 8
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 9
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 10
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.