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

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

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?

Consider the following deterministic finite state automaton M.

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

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?

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?

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.

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?

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?

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?

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?

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?

Which of the following problems is undecidable?

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?

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?

Which of the following is TRUE?

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?

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

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?

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?

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?