Compilers

Context Free Grammar

Question 1
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 2
Marks : +2 | -2
Pass Ratio : 100%
Recursively enumerable languages are not closed under ______________
Union
Intersection
Complementation
Concatenation
Explanation:
Recursive languages are closed under the following operations.
Question 3
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 4
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 5
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 6
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 7
Marks : +2 | -2
Pass Ratio : 100%
Assume the statements S1 and S2 given as:
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 proof of S1 can be seen in various book of theory of computation but s2 is a problem of category undecidable so a contradiction to this assumption can be easily obtained.
Question 8
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 9
Marks : +2 | -2
Pass Ratio : 100%
A regular Grammar is a _________
CFG
Non CFG
English Grammar
None of the mentioned
Explanation:
Regular grammar is CFG. It restricts its rules to a single non terminal on left hand side.
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.