This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFL- Closure Properties/Decision Properties”.
1. The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
View Answer
Explanation: Context free languages are closed under the following operation: union, kleene and concatenation. For regular languages, we can add intersection and complement to the list.
2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1
View Answer
Explanation:
T->S|R
S->aSb
S->e
R->cRd
R->e
3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
View Answer
Explanation: It is a theorem which states that, Context free languages are not closed under operations like intersection and complement.
4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
View Answer
Explanation: These properties are termed as decision properties of a CFL and include a set of problems like infiniteness problem, emptiness problem and membership problem.
5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
View Answer
Explanation: In the process of removing useless symbols, if the starting symbol is also a part, the CFL can be then termed as empty; otherwise not.
6. Using the pumping constant n, If there is a string in the language of length between _____ and ____ then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
View Answer
Explanation: If there is a string in the language of length between n and 2n-1 then the language is infite else not. The idea is essentially the same for regular languages.
7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
View Answer
Explanation: CFL is closed under union, kleene and concatenation along with the properties reversal,homomorphism and inverse homomorphism but not difference and intersection.
8. If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned
View Answer
Explanation: Context free languages are not closed under difference, intersection and complement operations.
9. A___________ is context free grammar with atmost one non terminal in the right handside of the production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
View Answer
Explanation: A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S → ε
10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer
Explanation: Linear grammar is a subset of context free grammar which has atmost one non terminal symbol in the right hand side of the production.Thus, there exists some languages which are generated by Linear grammars.
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.
- Check Automata Theory Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Computer Science Books