250+ TOP MCQs on Intersection with Regular Languages and Answers

Automata Theory Multiple Choice Questions 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

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

Answer: b
Clarification: 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) a¹⁰⁰b¹⁰⁰
b) (a+b)*-{a¹⁰⁰b¹⁰⁰}
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: 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) {a¹⁰⁰b¹⁰⁰}
d) All of the mentioned

Answer: d
Clarification: {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

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

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

Answer: c
Clarification: 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
c) Linked List
d) None of the mentioned

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

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

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