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) Both (a) and (b)
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.
advertisement

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) Both (a) and (b)
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.

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.
advertisement

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.

6. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) Both (a) and (b)
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) Both (a) and (b)
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 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.

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.
advertisement

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
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn