# 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

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

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

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

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

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

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

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

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

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

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 