(41) The set which is not countable if we have ∑ = {a, b}, is
(A) Set of all languages over ∑ accepted by turing machine
(B) Set of all regular languages over ∑
(C) Set of all strings over ∑
(D) Set of all languages over ∑
ANSWER: Set of all languages over ∑
(42) How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
(A) n+1
(B) n+2
(C) n
(D) 2n
ANSWER: n+2
(43) Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is
(A) 10
(B) 01
(C) 101
(D) 110
ANSWER: 10
(44) The set that can be recognized by a deterministic finite state automaton is
(A) The set {1, 101, 11011, 1110111, …….}
(B) The set of binary string in which the number of 0’s is same as the number of 1’s
(C) 1, 2, 4, 8……2n ….. written in binary
(D) 1, 2, 4, 8……2n ….. written in unary
ANSWER: 1, 2, 4, 8……2n ….. written in binary
(45) Consider the four regular expressions given below;
a. (00)*( ε+0)
b. (00)*
c. 0*
d. 0(00)*
The equivalent regular expression out of the four is
(A) b and c
(B) c and d
(C) a and b
(D) a and c
ANSWER: a and c
(46) L1 = Φ and L2 = {a} are the two languages. Out of the following four options the one that represents L1L2* U L1* is
(A) Φ
(B) a*
(C) {ε}
(D) {ε, a}
ANSWER: {ε}
(47) We have the language L = {ab, aa, baa} and the four strings given below:
I) abaabaaabaa
II) aaaabaaaa
III) baaaaabaaaab
IV) baaaaabaa
The strings present in L* are
(A) I, II and IV
(B) I, II and III
(C) II, III and IV
(D) I, III and IV
ANSWER: I, II and IV
(48) Which one of the following is true regarding FOTRAN?
(A) It is a context free language
(B) It is a context sensitive language
(C) It is a regular language
(D) None of the above
ANSWER: It is a context sensitive language
(49) The feature that cannot be captured by context free grammar is
(A) Recursive procedure Syntax
(B) Syntax of if-then-else statement
(C) Arbitrary length of variable names
(D) Variable declared before its use
ANSWER: Variable declared before its use
(50) Which one of the following is applicable for context free languages?
(A) These are closed under union, Kleene closure
(B) These are closed under complement, Kleene closure
(C) These are closed under union, intersection
(D) These are closed under intersection, complement
ANSWER: These are closed under union, Kleene closure