(21) State table of an FSM is given below. There are two states A And B, one input and one output.
Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
(A) 2
(B) 7
(C) 4
(D) 3
ANSWER: 3
For questions 22 and 23 refer to the data given below:
The figure shown below is a finite state automaton
(22) Which one of the following is true for this automaton?
(A) b*ab*ab*ab*
(B) b*a(a+b)*
(C) b*ab*ab*
(D) (a+b)*
ANSWER: b*a(a+b)*
(23) For the above FSA the equivalent minimum state automaton has the following number of states
(A) 1
(B) 2
(C) 3
(D) 4
ANSWER: 2
(24) Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
(A) P3 is decidable if P3 is reducible to compliment of P2
(B) P3 is decidable if P1 is reducible to P3
(C) P3 is undecidable if P1 is reducible to P3
(D) P3 is undecidable if P2 is reducible to P3
ANSWER: P3 is undecidable if P2 is reducible to P3
(25) G = {S->SS, S->ab, S->ba, S->?} is the context free grammar whose statements are given below:
a. G is ambiguous
b. G produces all strings with equal number of a’s and b’s.
c. Deterministic PDA accepts G
Which of the following statement is true about G?
(A) a, b, c all are true
(B) Only and b are true
(C) Only b and c are true
(D) Only a is true
ANSWER: a, b, c all are true
(26) The minimum number of states in any DFA accepting the regular language L = (111+11111)* is
(A) 5
(B) 7
(C) 9
(D) 11
ANSWER: 9
(27) Consider the language L = {W I W ∈ {0, 1}*, where 0’s and 1’s in W are divisible by 3 and 5 respectively. The minimum state deterministic finite automaton accepting the language L has
(A) 20 states
(B) 5 states
(C) 10 states
(D) 15 states
ANSWER: 15 states
(28) We have an undirected graph G(V, E) with two problems given below:
α – Does G have an independent set of size IVI – 4?
β – Does G have an independent set of size 5?
The statement that holds true is
(A) α is NP-complete and β is in P
(B) α is in P and β is NP-complete
(C) Both α and β are NP-complete
(D) Both α and β are in P
ANSWER: α is in P and β is NP-complete
(29) Figure shows deterministic finite state automaton M. Let the set of seven bit binary strings whose 1st, 4th and the last bits are 1 is denoted by S. How many strings in S is accepted by M?
(A) 1
(B) 9
(C) 3
(D) 5
ANSWER: 5
(30) Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
(A) L must be either {an I n is odd} or {an I n is even}
(B) L must be {an I n is odd}
(C) L must be {an I n is even}
(D) L must be {an I n = 0}
ANSWER: L must be either {an I n is odd} or {an I n is even}
(31) Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
(A) Only DHAM3 is NP-hard
(B) Only SHAM3 is NP-hard
(C) Both SHAM3 and DHAM3 are NP-hard
(D) Neither SHAM3 nor DHAM3 is NP-hard
ANSWER: Both SHAM3 and DHAM3 are NP-hard
(32) Which one of the following is true for the language {am bn c m+n I m, n≥1}?
(A) It is context-free but not regular
(B) It is regular
(C) It is type-0 but not context-sensitive
(D) It is context-sensitive but not context-free
ANSWER: It is regular
(33) We have decision problems P1 and P2 as described below:
P1: Does a given finite state machine accept a given string?
P2: Does a given context-free grammar generate an infinite number of strings?
The statement that holds true for P1 and P2 is
(A) Only P2 is decidable
(B) Only P1 is decidable
(C) Neither P1 nor P2 are decidable
(D) Both P1 and P2 are decidable
ANSWER: Both P1 and P2 are decidable
(34) Problem X is given below:
We have a turing machine M over the input alphabet ∑, any state q of M and a word W ∈ ∑*, does the computation of M on W visit the state q? The statement, which holds true
about X, is
(A) X is undecidable but partially decidable
(B) X is decidable
(C) X is not a decision problem
(D) X is undecidable and not even partially decidable.
ANSWER: X is undecidable but partially decidable
(35) The state diagram describes the finite state machine. A is the starting state and an arc label is x/y where x stands for 1 bit input and y stands for 2 bit output
(A) Whenever the input sequence is 10 it outputs 00
(B) Whenever the input sequence is 11 it outputs 01
(C) It outputs the sum of the present and the previous bits of the input
(D) None of the above
ANSWER: It outputs the sum of the present and the previous bits of the input
(36) Which one of the following statement is true for the C language?
(A) It is a regular language
(B) It is context-sensitive language
(C) It is context-free language
(D) It is parsable fully only by a turing machine
ANSWER: It is context-free language
(37) How many states are present in the smallest finite automaton which accepts the language {x I length of x is divisible by 3}?
(A) 5
(B) 4
(C) 3
(D) 2
ANSWER: 4
(38) The last two symbols of L which is the set of all binary strings are same. In the minimum state deterministic finite state automaton, which is accepting L _____, states are present
(A) 4
(B) 6
(C) 3
(D) 5
ANSWER: 5
(39) The true regular expression is
(A) (r*s*)* = (r+s)*
(B) (r+s)* = r* + s*
(C) r*s* = r* + s*
(D) r(*) = r*
ANSWER: (r*s*)* = (r+s)*
(40) Let n be the length of a character string. How many substrings (of all lengths inclusive) can be formed from n?
(A) n(n-1)/2
(B) n²
(C) (n (n+1)/2) + 1
(D) n
ANSWER: (n (n+1)/2) + 1