 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.

#### Important Notice!

Dear users, compscibits.com is now permanently moved to compsciedu.com. Please update all your links and bookmarks accordingly. Soon, the site will be accessible through URL compsciedu.com only.

 1. Given the language L = {ab, aa, baa}, which of the following strings are in L*?1) abaabaaabaa2) aaaabaaaa3) baaaaabaaaab4) baaaaabaa a. 1, 2 and 3 b. 2, 3 and 4 c. 1, 2 and 4 d. 1, 3 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

 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

 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

 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

 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

 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