Q. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}

Which one of the following choices precisely represents the strings in X0?

View solution

Q. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________

View solution

Q. Let T be the language represented by the regular expression Σ∗0011Σ∗ where Σ = {0, 1}. What is the minimum number of states in a DFA that recognizes L' (complement of L)?

View solution

Q. Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?

View solution

Q. Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language Lc∪ Mc is TRUE?

View solution

Q. Which of the following statements is TRUE about the regular expression 01*0?

View solution

Q. The language {0^n 1^n 2^n | 1 ≤ n ≤ 10^6} is

View solution

Q. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

View solution

Q. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?

View solution

Q. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?

View solution

Q. The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ .

View solution

Q. Consider the following two statements:

I. If all states of an NFA are accepting
states then the language accepted by
the NFA is Σ∗ .
II. There exists a regular language A such
that for all languages B, A ∩ B is regular.

Which one of the following is CORRECT?

View solution

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