1.  Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa 
a.  1, 2 and 3 
b.  2, 3 and 4 
c.  1, 2 and 4 
d.  1, 3 and 4 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).1, 2 and 4

2.  Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a nondeterministic finite automaton that accepts L? 
a.  n1 
b.  n 
c.  n+1 
d.  2n1 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).n+1

3.  Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? 
a.  The set of all strings containing the substring 00 
b.  The set of all strings containing at most two 0’s 
c.  The set of all strings containing at least two 0’s 
d.  The set of all strings that begin and end with either 0 or 1 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).The set of all strings containing at least two 0’s

4.  Which one of the following is FALSE? 
a.  There is unique minimal DFA for every regular language 
b.  Every NFA can be converted to an equivalent PDA 
c.  Complement of every contextfree language is recursive 
d.  Every nondeterministic PDA can be converted to an equivalent deterministic PDA 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Every nondeterministic PDA can be converted to an equivalent deterministic PDA

5.  Which of the following statements is false? 
a.  Every NFA can be converted to an equivalent DFA 
b.  Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine 
c.  Every regular language is also a contextfree language 
d.  Every subset of a recursively enumerable set is recursive 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Every subset of a recursively enumerable set is recursive

6.  Which of the following is TRUE? 
a.  Every subset of a regular set is regular 
b.  Every finite subset of a nonregular set is regular 
c.  The union of two nonregular sets is not regular 
d.  Infinite union of finite sets is regular 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Every finite subset of a nonregular set is regular

7.  A minimum state deterministic finite automaton accepting the language L={w  w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has 
a.  15 states 
b.  11 states 
c.  10 states 
d.  9 states 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).15 states

8.  Let L1 = {w ∈ {0,1}∗  w has at least as many occurrences
of (110)’s as (011)’s}. Let L2 = { ∈ {0,1}∗  w has at least as many occurrences 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 L! 
c.  Both L2 and L1 are regular 
d.  Neither L1 nor L2 are regular 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).L1 is regular but not L2

9.  The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.
a*b*(ba)*a* 
a.  2 
b.  3 
c.  4 
d.  5 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).3

10.  Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is: 
a.  3 
b.  5 
c.  8 
d.  9 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).9
