Compilers

Context Free Grammar

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