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
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
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
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
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
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) CYK algorithm and Exhaustive search parser
d) None of the mentioned
View Answer
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
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
c) Linked List
d) None of the mentioned
View Answer
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
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
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.
- Buy Automata Theory Books
- Apply for Automata Theory Internship
- Buy Computer Science Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
