250+ TOP MCQs on Context Free Grammar and Answers

Compilers Quiz on “Context Free Grammar”.

1. 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?
a) S1 is correct and S2 is not correct
b) Both S1 and S2 are correct
c) Both S1 and S2 are not correct
d) S1 is not correct and S2 is correct

Answer: b
Clarification: The assumptions of statement S1 and S2 are correct.

2. A context free language is called ambiguous if _________
a) It has 2 or more left derivations for some terminal string ѡ є L (G)
b) It has 2 or more right derivations for some terminal string ѡ є L (G)
c) It has 2 or more left & right derivations for some terminal string ѡ є L (G)
d) None of the mentioned

Answer: b
Clarification: A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.

3. Which of the following statement is false?
a) The CFG can be converted to Chomsky normal form
b) The CFG can be converted to Greibach normal form
c) CFG is accepted by pushdown automata
d) None of the mentioned

Answer: d
Clarification: All the statements follow the rules.

4. The context free grammar S → A111|S1, A → A0 | 00 is equivalent to _________
a) {0ⁿ1^m | n=2, m=3}
b) {0ⁿ1^m | n=1, m=5}
c) {0ⁿ1^m | n should be greater than two and m should be greater than four}
d) None of the mentioned

Answer: a
Clarification: S-> A111
S->00111 (A->00).

5. The context free grammar S → SS | 0S1 | 1S0 | ɛ generates _________
a) Equal number of 0’s and 1’s
b) Unequal number of 0’s and 1’s
c) Number of 0’s followed by any number of 1’s
d) None of the mentioned

Answer: a
Clarification: S->SS
S->0S1S
S->0S11S0
S->0110.

6. Which of the following statement is false?
a) In derivation tree, the label of each leaf node is terminal
b) In derivation tree, the label of all nodes except leaf nodes is a variable
c) In derivation tree, if the root of a sub tree is X then it is called –tree
d) None of the mentioned

Answer: d
Clarification: All of them are true regarding a derivation tree.

7. Push down automata accepts which language?
a) Context sensitive language
b) Context free language
c) Recursive language
d) None of the mentioned

Answer: b
Clarification: PDA accepts CFG.

8. A regular Grammar is a _________
a) CFG
b) Non CFG
c) English Grammar
d) None of the mentioned

Answer: a
Clarification: Regular grammar is CFG. It restricts its rules to a single non terminal on left hand side.

9. A CFG is closed under _________
a) Union
b) Kleene star
c) Concatenation
d) None of the mentioned

Answer: d
Clarification: CFG is closed under the above mentioned 3 operations.

10. Which of these does not belong to CFG?
a) Terminal Symbol
b) Non terminal Symbol
c) Start symbol
d) End Symbol

Answer: d
Clarification: CFG consists of terminal non terminal start symbol set of production rules but does not have an end symbol.