Automata Theory Multiple Choice Questions 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
Answer: c
Clarification: 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
Answer: a
Clarification:
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
Answer: d
Clarification: 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
Answer: d
Clarification: 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: 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.