This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Eliminating Unit Productions”.
1. Which of the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
View Answer
Explanation: Any production of the format A-> B where A and B belongs to the V set, is called Unit production.
2. Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The productions in the format A-> A are removed immediately as they produce self and that is not a terminal or will not lead to a string. Hence, it is removed immediately.
3. Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb
View Answer
Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
4. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said
View Answer
Explanation: With the simplification of Context free grammars, undesirable properties are introduced. It says, if grammar G, before simplification is unambiguous, after simplification will also be unambiguous.
5. If C is A-derivable, C->B is a production, and B ¹ A, then B is
a) nullable
b) Non-derivable
c) A-derivable
d) None of the mentioned
View Answer
Explanation:
If A-> B is a production, B is called A- derivable.
If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.
No other variables are A-derivable.
6. A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: The format says: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a production : A-> A need to exist.
7. Given Grammar:
T-> T+R| R
R-> R*V| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->R*V|(T)| u
V-> (T)| u
Fill in the blank:
a) T*V
b) T+V
c) R*T
d) R*V
View Answer
Explanation: The grammar produced after the elimination of unit production is:
T-> T+R| R*V| (T)| u
R->R*V|(T)| u
V-> (T)| u
8. Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable holds?
a) 6
b) 7
c) 9
d) 5
View Answer
Explanation: After reduction the grammar looks like:
S->ABA| AB| BA| AA| Aa| a| bB| b
A->aA| a
B->bB| b
9. Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a) 5
b) 4
c) 3
d) 2
View Answer
Explanation: The reduced production:
S->aAa| bB|bb aCaa| baD| abD| aa, A->aAa| bB| bb, B->bB| bb, C->aCaa| baD| abD| aa, D-> baD| abD| aa
10. Which of the following variables in the given grammar is called live variable?
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned
View Answer
Explanation: Any variable A for which there is a production A-> x with x Ε Σ* is called live.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Automata Theory Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Computer Science MCQs
