Automata Theory Questions and Answers – Eliminating Unit Productions

«
»

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

Answer: a
Explanation: Any production of the format A-> B where A and B belongs to the V set, is called Unit production.
advertisement

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

Answer: c
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

Answer: b
Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

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

Answer: b
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

Answer: c
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.
advertisement

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

Answer: a
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

Answer: d
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
advertisement

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

Answer: b
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

Answer: a
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
advertisement

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

Answer: b
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.