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.

131. Consider the language L1,L2,L3 as given below.

L1={0^p1^q | p,q ∈ N}
L2={0^p1^q| p,q ∈ N and p=q}
L3={0^p1^q0^r | p,q,r ∈N and p=q=r}
Which of the following statements is NOT TRUE?
a. Push Down Automata (PDA) can be used to recognize L1 and L2
b. L1 is a regular language
c. All the three languages are context free
d. Turing machine can be used to recognize all the three languages
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).All the three languages are context free

132. Definition of a language L with alphabet {a} is given as following. L= { a^(nk) | k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L?
a. k+1
b. n+1
c. 2^(n+1)
d. 2^(k+1)
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).n+1

133. Which of the following pairs have DIFFERENT expressive power?
a. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
b. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
c. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
d. Single-tape Turing machine and multi-tape Turing machine
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

134. Which of the following problems are decidable?

1) Does a given program ever produce an output?
2) If L is a context-free language, then is L’ (complement of L) also context-free?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
a. 1, 2, 3, 4
b. 1, 2
c. 2, 3, 4
d. 3, 4
View Answer Report Discuss Too Difficult!
Answer: (d).3, 4

135. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
a. ScT (S is a subset of T)
b. TcS (T is a subset of S)
c. S=T
d. SnT=Ø
View Answer Report Discuss Too Difficult!
Answer: (c).S=T

136. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true ?
a. L = O
b. L is regular but not O
c. L is context free but not regular
d. L is not context free
View Answer Report Discuss Too Difficult!
Answer: (b).L is regular but not O

137. Consider the following two statements:

S1: { 0^2n |n >= l} is a regular language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language

Which of the following statements is correct?
a. Only S1 is correct
b. Only S2 is correct
c. Both S1 and S2 are correct
d. None of S1 and S2 is correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both S1 and S2 are correct

138. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
a. N^2
b. 2^N
c. 2N
d. N!
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).2^N

Page 14 of 14