Q. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

View solution

Q. Consider the following languages.

L1 = {a^i b^j c^k | i = j, k ≥ 1}
L1 = {a^i b^j | j = 2i, i ≥ 0}

Which of the following is true?

View solution

Q. Which of the following languages is (are) non-regular?

L1 = {0^m1^n | 0 ≤ m ≤ n ≤ 10000}
L2 = {w | w reads the same forward and backward}
L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

View solution

Q. Which of the following intuitive definition is true about LR(1) Grammar.

View solution

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