1. A language is regular if and only if?
a) Accepted by DFA
b) Accepted by PDA
c) Accepted by LBA
d) Accepted by Turing machine
Explanation: All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
2. What is Regular grammar?
a) Context free grammar
b) Non context free grammar
c) English grammar
d) None of the mentioned
Explanation: Regular grammar is subset of context free grammar.
3. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then?
a) L1<l2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2
Explanation: Finite state machine and regular expression have same power to express a language.
4. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*
Explanation: Except [(0+1)-(0b+a1)*(a+b)]* all are regular expression.
5. Regular expression is __________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
Explanation: According to the Chomsky hierarchy.
6. Which of the following is true?
a) All subsets of a regular set are always regular
b) All finite subsets of non-regular set are always regular
c) Union of two non regular set of language is not regular
d) Infinite times union of finite set is always regular
Explanation: All finite subsets of non-regular set are always regular
7. L and ~L are recursive enumerable then L is?
a) Regular
b) Context free
c) Context sensitive
d) Recursive
Explanation: If L is recursive enumerable and its complement too if and only if L is recursive.
8. Regular expressions are closed under _____________
a) Union
b) Intersection
c) Kleene star
d) All of the mentioned
Explanation: According to the definition of regular expression.
9. Give a production grammar that specified language L = {ai b2i >= 1}.
a) {S->aSbb,S->abb}
b) {S->aSb, S->b}
c) {S->aA,S->b,A->b}
d) None of the mentioned
Explanation: S->aSbb, S->abb give a^I a’s and b^2i b’s.
10. Let R1 and R2 be regular sets defined over alphabet ∑ then?
a) R1 UNION R2 is regular
b) R1 INTERSECTION R2 is regular
c) ∑ INTERSECTION R2 IS NOT REGULAR
d) R2* IS NOT REGULAR
Explanation: Union of 2 regular languages is regular.