Deck 4: Omputer Science and Theory of Computation

Question 1

The symbols that can't be replaced by anything are called -----------------

A)Productions
B)Terminals
C)Non-terminals
D)All of above

Answer 1

Terminals

Question 2

Left hand side of a production in CFG consists of:

A)One terminal
B)More than one terminal
C)One non-terminal
D)Terminals and non-terminals

Answer 2

Terminals and non-terminals

Question 3

Choose the incorrect statement:

A)(a+b)aa(a+b)generates Regular language.
B)A language consisting of all strings over ?={a,b} having equal number of a's and b's is a regular language
C)Every language that can be expressed by FA can also be expressed by RE
D)None of these

Answer 3

None of these

Question 4

Choose the incorrect statement.

A)A Mealy machine generates no language as such
B)A Mealy machine has no terminal state
C)For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine
D)All of these

Question 5

In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called

A)Dead State
B)Waste Basket
C)Davey John Locker
D)All of these

Question 6

Which statement is true?

A)The tape of turing machine is infinite.
B)The tape of turing machine is finite.
C)The tape of turing machine is infinite when the language is regular
D)The tape of turing machine is finite when the language is nonregular.

Question 7

If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:

A)(r1)(r2)
B)(r1 + r2)
C)(r2)(r1)
D)(r1)

Question 8

Which of the following will be used for text searching application-?

A)NFA
B)DFA
C)PDA
D)None of these

Question 9

Context free grammar is used for-

A)Lexical analyzer
B)Document type definition (DTD)
C)Text pattern searching
D)Both a & c

Question 10

The set strings of 0's and 1's with atmost one pair consecutive one's-

A)(0+1)*(01)(10)(0+1)*
B)(0+1)*(01)*(10)(0+1)*
C)(0+1)*(01)(10)*(0+1)*
D)(0+!)(01)*(10)*(0+1)

Question 11

The problem 3-SAT and 2-SAT are

A)Both in P
B)Both NP complete
C)NP-complete and in P respectively
D)Undecidable and NP-complete respectively

Question 12

Which of the following instances of the post correspondence problem has a viable sequence (a solution)?

A){(b, bb), (bb, bab), (bab, abb), (abb, babb)}
B){(ab, aba), (baa, aa), (aba, baa)}
C){(ab, abb), (ba, aaa), (aa, a)}
D)none of the above

Question 13

Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?

A)Both FHAM and DHAM are NP-hard
B)FHAM is NP hard, but DHAM is not
C)DHAM is NP hard, but FHAM is not
D)Neither FHAM nor DHAM is NP hard

Question 14

Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.

A)P3 has polynomial time solution if P1 is polynomial time reducible to P3
B)P3 is NP complete if P3 is polynomial time reducible to P2
C)P3 is NP complete if P2 is reducible to P3
D)P3 has polynomial time complexity and P3 is reducible to P2

Question 15

Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet ??

A)L is undecidable
B)L is recursive
C)L is a CSL
D)L is a regular set

Question 16

Which one of the following is not decidable?

A)given a Turing machine M, a string s, and an integer k, M accepts s with k steps
B)equivalence of two given Turing machines
C)language accepted by a given DFSA is nonempty
D)language generated by a CFG is nonempty

Question 17

Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

A)1, 2 and 3
B)1 and 2 only
C)2 and 3 only
D)1 and 3 only

Question 18

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

Question 19

Which of the following statement is false for a turing machine?

A)There exists an equivalent deterministic turing machine for every nondeterministic turing machine
B)Turing decidable languages are closed under intersection and complementation
C)Turing recognizable languages are closed under union and intersection
D)Turing recognizable languages are closed under union and complementation

Question 20

Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

A)P is NP-complete
B)P is NP-hard but not NP-complete
C)P is in NP but not NP-complete
D)P is neither NP-hard nor in NP

Question 21

3-SAT and 2-SAT problems are

A)NP-complete and in P respectively
B)Undecidable and NP-complete
C)Both NP-complete
D)Both in P

Question 22

Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be

A)2k + 1
B)k + 1
C)2n + 1
D)n + 1

Question 23

Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as

A)Regular
B)Deterministic context free
C)Context free
D)Recursive

Question 24

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

Question 25

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