Automata Theory Questions and Answers – Intersection with Regular Languages

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Intersection with Regular Languages”.

1. Which of the following is not a negative property of Context free languages?
a) Intersection
b) Complement
c) Intersection and Complement
d) None of the mentioned
View Answer

Answer: c
Explanation: Context free languages are not closed under complement and intersection. Thus, are called Negative properties.

2. The intersection of context free language and regular language is _________
a) regular language
b) context free language
c) context sensitive language
d) non of the mentioned
View Answer

Answer: b
Explanation: If a language L1 is regular and L2 is a context free language, then L1 intersection L2 will result into a context free language.

3. Which of the following is regular?
a) a100b100
b) (a+b)*-{a100b100}
c) a100b100 and (a+b)*-{a100b100}
d) None of the mentioned
View Answer

Answer: c
Explanation: As the language seems to be finite, a dfa can be constructed for the same, thus is regular.
advertisement
advertisement

4. Which of the following is not context free?
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned
View Answer

Answer: d
Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.

5. Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned
View Answer

Answer: c
Explanation: We can use the properties of regular closure to prove that a language is not a context free language. Example: Intersection of context free language and regular language is a context free language. Proof by contradiction helps here.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) CYK algorithm and Exhaustive search parser
d) None of the mentioned
View Answer

Answer: c
Explanation: CYK algorithm is a parsing algorithm for context free grammars, which employs bottom up parsing and dynamic programming.

7. Which of the following belong to the steps to prove emptiness?
a) Remove useless variable
b) Check if a start variable S is useless
c) Remove useless variable and Check if a start variable S is useless
d) None of the mentioned
View Answer

Answer: c
Explanation: The empty-language question can be stated as: For context free grammar G find if L(G) =f?
advertisement

8. Which of the following is true for CYK Algorithm?
a) Triangular Table
b) Circular Chart
c) Linked List
d) None of the mentioned
View Answer

Answer: a
Explanation: A triangular table is constructed to facilitate the solution of membership problem using bottom up parsing and dynamic programming.

9. Which of the following steps are wrong with respect to infiniteness problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the language is finite else infinite
View Answer

Answer: d
Explanation: If we are able to detect a loop in the formed dependency graph, then the language in infinite.
advertisement

10. State true or false:
Statement: Every context free language can be generated by a grammar which contains no useless non terminals.
a) true
b) false
View Answer

Answer: a
Explanation: At first, we detect useless symbols and discard them. Inorder to find whether a symbol is useless, just make it the starting symbol and check for emptiness.

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.