Q. In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?

View solution

Q. Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?

View solution

Q. Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?

View solution

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