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