Automata Theory Questions and Answers – CFL- Closure Properties/Decision Properties

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFL- Closure Properties/Decision Properties”.

1. The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
View Answer

Answer: c
Explanation: Context free languages are closed under the following operation: union, kleene and concatenation. For regular languages, we can add intersection and complement to the list.

2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1
View Answer

Answer: a
Explanation:
T->S|R
S->aSb
S->e
R->cRd
R->e

3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
View Answer

Answer: d
Explanation: It is a theorem which states that, Context free languages are not closed under operations like intersection and complement.
advertisement
advertisement

4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
View Answer

Answer: d
Explanation: These properties are termed as decision properties of a CFL and include a set of problems like infiniteness problem, emptiness problem and membership problem.

5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
View Answer

Answer: b
Explanation: In the process of removing useless symbols, if the starting symbol is also a part, the CFL can be then termed as empty; otherwise not.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Using the pumping constant n, If there is a string in the language of length between _____ and ____ then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
View Answer

Answer: a
Explanation: If there is a string in the language of length between n and 2n-1 then the language is infite else not. The idea is essentially the same for regular languages.

7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
View Answer

Answer: d
Explanation: CFL is closed under union, kleene and concatenation along with the properties reversal,homomorphism and inverse homomorphism but not difference and intersection.
advertisement

8. If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned
View Answer

Answer: c
Explanation: Context free languages are not closed under difference, intersection and complement operations.

9. A___________ is context free grammar with atmost one non terminal in the right handside of the production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
View Answer

Answer: a
Explanation: A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S → ε
advertisement

10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer

Answer: c
Explanation: Linear grammar is a subset of context free grammar which has atmost one non terminal symbol in the right hand side of the production.Thus, there exists some languages which are generated by Linear grammars.

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]

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 & discussions at Telegram SanfoundryClasses.