Q. Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then

View solution

Q. Consider the following decision problems:

(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite
number of stings

Which of the following statements is true?

View solution

Q. Which of the following statements is true ?

View solution

Q. Consider the following problem X.

Given 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?

Which of the following statements about X is correct?

View solution

Q. The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as

View solution

Q. Which of the following is true?

View solution

Q. The C language is:

View solution

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

View solution

Q. Nobody knows yet if P = NP. Consider the language L defined as follows. Which of the following statements is true ?

View solution

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

View solution

Q. Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε . Which of the following statements is true?

View solution

Q. Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts 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 = L0 ∪ L1. Which of the following is true ?

View solution

Q. The language {a^m b^n C^(m+n) | m, n ≥ 1} is

View solution

Q. Consider the following grammar G:

S → bS | aA | b
A → bA | aB
B → bB | aS | a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

View solution

Q. L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.

S1 : L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive

Which of the following statements is true ?

View solution

Q. Consider the languages L1 = {0^i1^j | i != j}. L2 = {0^i1^j | i = j}. L3 = {0^i1^j | i = 2j+1}. L4 = {0^i1^j | i != 2j}.

View solution

Q. S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

View solution

Q. The language L= {0^i21^i | i≥0 } over the alphabet {0,1, 2} is:

View solution

Q. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA

Which of the following strings is generated by the grammar?

View solution

Q. Consider the following statements about the context free grammar

G = {S → SS, S → ab, S → ba, S → Ε}
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?

View solution