Q. Consider the Following regular expressions

r1 = 1(0 + 1)*
r2 = 1(1 + 0)+
r3 = 11*0

What is the relation between the languages generated by the regular expressions above ?

View solution

Q. Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are:

View solution

Q. Consider the grammar G.

E -> TE’
E’ -> +TE’ | ԑ
T’ -> FT’
T’ -> *FT’ | ԑ
F -> (E) | id

If LL(1) parsing table is constructed using the grammar G, then how many entries are present in the row that represents E’ nonterminal ? (consider the entries which are not error/not blank entries)

View solution

Q. Let, init (L) = {set of all prefixes of L},
Let L = {w | w has equal number of 0’s and 1’s}
init (L) will contain:

View solution

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