A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table. | | 0 | 1 | B | |----|----------|----------|----------| | q0 | q1, 1, R | q1, 1, R | Halt | | q1 | q1, 1, R | q0, 1, L | q0, B, L | The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M?

M does not halt on any string in (0+1) +

If s is a string over (0 + 1)* then let n 0 (s) denote the number of 0's in s and n 1 (s) the number of 1's in s. Which one of the following languages is not regular?

L = {s $\in$(0 + 1)*| n 0 (s') - n 1 (s')| $\le$4 |

Test 1 - Theory of Computation | Computer Science(CS)

Question 1 Multiple Choice (Single Answer)

The regular expression 0*(10*)* denotes the same set as

(1*0)1
0+(0+10)*
(0+1)10(0+1)
None of these

Question 2 Multiple Choice (Single Answer)

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

L is necessarily finite
L is regular but not necessarily finite
L is context free but not necessarily regular
L is recursive but not necessarily context free

Question 3 Multiple Choice (Single Answer)

Nobody knows yet if P = NP. Consider the language L defined as follows.

$$L = \begin{cases} (0 +1)^* \text { if } (P = NP) \in E \\ \phi \text{ otherwise} \end{cases}$$

Which of the following statements is true?

L is recursive
L is recursively enumerable but not recursive
L is not recursively enumerable
Whether L is recursive or not will be known after we find out if P = NP

Question 4 Multiple Choice (Single Answer)

Consider the following deterministic finite state automaton M.

GATE 2003
Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

1
5
7
8

Question 5 Multiple Choice (Single Answer)

Ram and Shyam have been asked to show that a certain problem ^$\prod$is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to^$\prod$, and Shyam shows a polynomial time reduction from ^$\prod$to 3-SAT. Which of the following can be inferred from these reductions?

^$\prod$ is NP-hard but not NP-complete
^$\prod$is in NP, but is not NP-complete
^$\prod$is NP-complete
^$\prod$is neither NP-hard, nor in NP

Question 6 Multiple Choice (Single Answer)

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

R is NP-complete
R is NP-hard
Q is NP-complete
Q is NP-hard

Question 7 Multiple Choice (Single Answer)

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0,1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

	0	1	B
q0	q1, 1, R	q1, 1, R	Halt
q1	q1, 1, R	q0, 1, L	q0, B, L
The table is interpreted as illustrated below.
The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape
square, then it writes 1 on the same tape square, moves its tape head one position to the right and
transitions to state q1.

Which of the following statements is true about M?

M does not halt on any string in (0+1)⁺
M does not halt on any string in (00+1)*
M halts on all strings ending in a 0
M halts on all strings ending in a 1

Question 8 Multiple Choice (Single Answer)

Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S $\rightarrow$ a S b | S S | $\epsilon$
Which of the following statements is true?

G is not ambiguous
There exist x, y $\epsilon$ L(G) such that xy $\require{cancel} \cancel{\epsilon}$ L(G)
There is a deterministic pushdown automaton that accepts L(G)
We can find a deterministic finite state automaton that accepts L(G)

Question 9 Multiple Choice (Single Answer)

Consider the NFA M shown below.

Let the language accepted by M be L. Let L₁ be the language accepted by the NFA M₁ obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting states of M to accepting states. Which of the following statements is true?

L₁ = {0,1}* - L
L₁ = {0,1}*
L_{1$\subseteq $} L
L₁ = L

Question 10 Multiple Choice (Single Answer)

Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$.

Let $f: \Sigma \to \Sigma$ be a polynomial time, computable bijection, such that:

$$\forall x: \Bigl(x \in L_1 \iff f(x) \in L_2\Bigr )$$

Further, let $f^{-1}$ also be polynomial time computable.

Which of the following canNOT be true?

L₁ $\epsilon$ P and L₂ is finite
L₁ $\epsilon$ NP and L₂ $\epsilon$ P
L₁ is un decidable and L₂ is decidable
L₁ is recursively enumerable and L₂ is recursive

Question 11 Multiple Choice (Single Answer)

Let SHAM_, be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with V divisible by 3 and DHAM' be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Both DHAM, and SHAM, are NP-hard
SHAM, is NP-hard, but DHAM,is not
DHAM, is NP-hard, but SHAM, is not
Neither DHAM, nor SHAM, is NP-hard

Question 12 Multiple Choice (Single Answer)

Which of the following problems is undecidable?

Membership problem for CFGs.
Ambiguity problem for CFGs.
Finiteness problem for FSAs.
Equivalence problem for FSAs.

Question 13 Multiple Choice (Single Answer)

Define languages L0 and L1 as follows:
L₀ = {<M, w, 0> | M halts on w}
L₁ = {<M, w, 1> | M does not halt on w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a Turing
Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L_0$\cup$L₁. Which of the following is true?

L is recursively enumerable, but $\bar L$ is not
$\bar L$ is recursively enumerable, but L is not
Both L and $\bar L$ are recursive
Neither L nor $\bar L$ is recursively enumerable

Question 14 Multiple Choice (Single Answer)

Let L₁ = {0^n+m1ⁿ0^m|n, m$\ge$0}. L₂ = {0^n+m1^n+m0^m|n, m$\ge$0} and L₃ = {0^n+m1^n+m0^n+m|n, m$\ge$0} Which of these languages are NOT context free?

L₁ only
L₂ only
L₁ and L₂
L₂ and L₃

Question 15 Multiple Choice (Single Answer)

Which of the following is TRUE?

Every subset of a regular set is regular.
Every finite subset of a non-regular set is regular.
The union of two non-regular sets is not regular.
Infinite union of finite sets is regular.

Question 16 Multiple Choice (Single Answer)

For S $\in$ (0 + 1) * let d (s) denote the decimal value of s (e.g. d (101) = 5).
Let L = {s $\in$ (0 + 1)* d (s)mod 5 = 2 and d (s) mod 7 $\ne$ 4}
Which one of the following statements is true?

L is recursively enumerable, but not recursive
L is recursive, but not context-free
L is context-free, but not regular
L is regular

Question 17 Multiple Choice (Single Answer)

Consider the regular language L = (111 + 11111) *. The minimum number of states in any DFA accepting these languages is:

3
5
8
9

Question 18 Multiple Choice (Single Answer)

If s is a string over (0 + 1)* then let n₀ (s) denote the number of 0's in s and n₁ (s) the number of 1's in s. Which one of the following languages is not regular?

L = {s $\in$(0 + 1)*| n₀ (s) is a 3-digit prime}
L = {s $\in$(0 + 1)*| for every prefix s' of s₁ |n₀ (s') - n₁ (s')| $\le$2 |
L = {s $\in$(0 + 1)*| n₀ (s') - n₁ (s')| $\le$4 |
L = {s $\in$(0 + 1)*| n₀ (s) mod 7 = n₁ (s) mod 5 = 0}

Question 19 Multiple Choice (Single Answer)

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

L₁ $\cap$ L is a deterministic CFL
L₃ $\cap$ L₁ is recursive
L₁ U L₂ is context free
L₁ $\cap$ L₂ $\cap$ L₃ is recursively enumerable

Question 20 Multiple Choice (Single Answer)

Consider the following statements about the context free grammar
G = {S $\rightarrow$ SS, S $\rightarrow$ ab, S $\rightarrow$ ba, S $\rightarrow$$\in$}
I. G is ambiguous
II. G produces all strings with equal number of a's and b's
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?

I only
I and III only
II and III only
I, II and III

Test 1 - Theory of Computation | Computer Science(CS)

Questions