1. 
= ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE? 
A.  L1 is regular but not L2 
B.  L2 is regular but not L1 
C.  Both L1 and L2 are regular 
D.  Neither L1 nor L2 are regular 
Answer» B. L2 is regular but not L1 
2. 
A spanning tree for a simple graph of order 24 has 
A.  12 edges 
B.  6 edges 
C.  23 edges 
D.  None of above. 
Answer» C. 23 edges 
3. 
If G is a simple connected 3regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is 
A.  3 
B.  4 
C.  6 
D.  5 
Answer» C. 6 
4. 
If G is a connected planar graph of v vertices e edges and r regions then 
A.  ve+r=2 
B.  ev+r=2 
C.  v+er=2 
D.  None of above. 
Answer» A. ve+r=2 
5. 
A Hamiltonian cycle in a Hamiltonian graph of order 24 has 
A.  12 edges. 
B.  24 edges 
C.  23 edges 
D.  None of above. 
Answer» B. 24 edges 
6. 
If G is a simple connected 3regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is 
A.  3 
B.  4 
C.  6 
D.  5 
Answer» C. 6 
7. 
The following grammar

A.  is type 3 
B.  is type 2 but not type 3 
C.  is type 1 but not type 2 
D.  is type 0 but not type 1 
Answer» B. is type 2 but not type 3 
8. 
The following grammar

A.  is type 3 
B.  is type 2 but not type 3 
C.  is type 1 but not type 2 
D.  is type 0 but not type 1 
Answer» C. is type 1 but not type 2 
9. 
The following grammar

A.  is type 3 
B.  is type 2 but not type 3 
C.  is type 1 but not type 2 
D.  is type 0 but not type 1 
Answer» A. is type 3 
10. 
P, Q, R are three languages. If P & R are regular and if PQ=R, then 
A.  Q has to be regular 
B.  Q cannot be regular 
C.  Q need not be regular 
D.  Q has to be a CFL 
Answer» C. Q need not be regular 
11. 
Which of the following is true with respect to Kleene’s theorem?

A.  1 only 
B.  2 only 
C.  Both 1 and 2 are true statements 
D.  None is true 
Answer» C. Both 1 and 2 are true statements 
12. 
Automaton accepting the regular expression of any number of a ' s is: 
A.  a* 
B.  ab* 
C.  (a/b)* 
D.  a*b*c 
Answer» A. a* 
13. 
Grammars that can be translated to DFAs: 
A.  Left linear grammar 
B.  Right linear grammar 
C.  Generic grammar 
D.  All of these 
Answer» B. Right linear grammar 
14. 
Two strings x and y are indistinguishable if: 
A.  δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y 
B.  if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A 
C.  Both above statements are true 
D.  None of the above 
Answer» C. Both above statements are true 
15. 
Given an arbitrary nondeterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least: 
A.  N2 
B.  2N 
C.  2N 
D.  N! 
Answer» C. 2N 
16. 
Regular expressions are 
A.  Type 0 language 
B.  Type 1 language 
C.  Type 2 language 
D.  Type 3 language 
Answer» A. Type 0 language 
17. 
The regular expression 0*(10)* denotes the same set as 
A.  (1*0)*1* 
B.  0+(0+10)* 
C.  (0+1)*10(0+1)* 
D.  None of the above 
Answer» B. 0+(0+10)* 
18. 
Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a nonaccepting state and by changing the nonaccepting state of M to accepting states. Which of the following statements is true? 
A.  L1 = {0,1}* − L 
B.  L1 = {0,1}* 
C.  L1 is a subset of L 
D.  L1 = L 
Answer» A. L1 = {0,1}* − L 
19. 
Which of the statements is true: 
A.  The complement of a regular language is always regular. 
B.  Homomorphism of a regular language is always regular. 
C.  Both of the above are true statements 
D.  None of the above 
Answer» C. Both of the above are true statements 
20. 
The regular sets are closed under: 
A.  Union 
B.  Concatenation 
C.  Kleene closure 
D.  All of the above 
Answer» D. All of the above 
21. 
Any given transition graph has an equivalent: 
A.  regular 
B.  DFSM (Deterministic Finite State Machine) 
C.  NDFSM 
D.  All of them 
Answer» D. All of them 
22. 
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 
Answer» A. Accepted by DFA 
23. 
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)* 
Answer» B. [(0+1)(0b+a1)*(a+b)]* 
24. 
Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is 
A.  3 
B.  5 
C.  8 
D.  9 
Answer» D. 9 
25. 
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*? 
A.  7 
B.  10 
C.  12 
D.  11 
Answer» D. 11 
We're developing a website for study materials for students.
We would love to hear your answers to some of the questions.