Ambiguous Grammar Automata Theory Multiple Choice Questions with Answers

Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Ambiguous Grammar”.

1. A CFG is ambiguous if
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
View Answer

Answer: b
Explanation: A context free grammar is ambiguous if it has more than one parse tree generated or more than one leftmost derivations. An unambiguous grammar is a context free grammar for which every valid string has a unique leftmost derivation.

2. Which of the following are always unambiguous?
a) Deterministic Context free grammars
b) Non-Deterministic Regular grammars
c) Context sensitive grammar
d) None of the mentioned
View Answer

Answer: a
Explanation: Deterministic CFGs are always unambiguous , and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.

3. A CFG is not closed under
a) Dot operation
b) Union Operation
c) Concatenation
d) Iteration
View Answer

Answer: d
Explanation: The closure property of a context free grammar does not include iteration or kleene or star operation.

4. Which of the following is an real-world programming language ambiguity?
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned
View Answer

Answer: a
Explanation: Dangling else problem: In many languages,the else in an if-then-else statement is optional, which results into nested conditionals being ambiguous, at least in terms of the CFG.

5. Which of the following is a parser for an ambiguous grammar?
a) GLR parser
b) Chart parser
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: c
Explanation: GLR parser: a type of parser for non deterministic and ambiguous grammar
Chart parser: aa type of parser for ambiguous grammar.

6. A language that admits only ambiguous grammar:
a) Inherent Ambiguous language
b) Inherent Unambiguous language
c) Context free language
d) Context Sensitive language
View Answer

Answer: a
Explanation: A context free language for which no unambiguous grammar exists, is called Inherent ambiguous language.

7. Which of the following is an example of inherent ambiguous language?
a) {aⁿ|n>1}
b) {aⁿbⁿc^md^m| n,m > 0}
c) {0ⁿ1ⁿ|n>0}
d) None of the mentioned
View Answer

Answer: b
Explanation: This set is context-free, since the union of two context-free languages is always context free.

8. State true or false:
Statement: R->R|T T->ε is an ambiguous grammar
a) true
b) false
View Answer

Answer: a
Explanation: The production can be either itself or an empty string. Thus the empty string has more than one leftmost derivations, depending on how many times R->R is being used.

9. In context to ambiguity, the number of times the following programming statement can be interpreted as:
Statement: if R then if T then P else V
a) 2
b) 3
c) 4
d) 1
View Answer

Answer: a
Explanation: Dangling else problem
if R then (if T then P else V) and if R then (if T then P) else V are the two ways in which the given if else statement can be parsed.

10. CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned
View Answer

Answer: CYK algorithm parses the CFG in polynomial time while LR parsers do the same in linear time. DCFGs are accepted by DPDAs and parsed using LR parsers or CYK algorithm.