A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

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 non-deterministic finite automaton that accepts L?
a. n-1
b. n
c. n+1
d. 2n-1
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 context-free 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 non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
c. Every regular language is also a context-free 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 non-regular set is regular
c. The union of two non-regular 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 non-regular 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

Page 1 of 14