(11) Which one of the following statement is true?
(A) The intersection of two context free languages is context free
(B) A context free language can always be accepted by a deterministic push down automaton
(C) The union of two context free languages is context free
(D) The complement of a context free language is context free.
ANSWER: The union of two context free languages is context free
(12) Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be
(A) 2k + 1
(B) k + 1
(C) 2n + 1
(D) n + 1
ANSWER: n + 1
(13) Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as
(A) Regular
(B) Deterministic context free
(C) Context free
(D) Recursive
ANSWER: Regular
(14) Which one of the following statement is true if L denotes the language generated by the grammar S->0S0/00?
(A) L is not context free
(B) L is regular but not 0+
(C) L = 0+
(D) L is context free but not regular
ANSWER: L is regular but not 0+
(15) Consider the regular expression 0 * (10 *) which is similar to the same set as
(A) 0 + (0 + 10) *
(B) (0 +1) * 10 (0 + 1) *
(C) (1 * 0) * 1*
(D) None of the above
ANSWER: None of the above
(16) W is any string whose length is n in {0, 1}* and L is the set of all sub-strings of W. The minimum number of states in a non-deterministic finite automaton that accepts L is
(A) n
(B) 2n
(C) n + 1
(D) n – 1
ANSWER: n + 1
(17) The DFA shown below accepts the set of all strings over {0, 1} that
(A) End with 00
(B) End with 0
(C) Begin either with 0 or 1
(D) Contain the substring 00
ANSWER: End with 00
(18) We have two statements S1 and S2 whose definition are as follows:
S1 – {02n In ≥ I} is a regular language.
S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language.
Which one of the following statements is correct?
(A) Both S1 and S2 are correct
(B) Only S2 is correct
(C) Only S1 is correct
(D) Neither S1 nor S2 is correct
ANSWER: Only S1 is correct
(19) Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is
(A) L = {s ∈ (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
(B) L = {s ∈ (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
(C) L = {s ∈ (0+1)* I no(s) is a 3 digit prime}
(D) L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4
ANSWER: L = {s ∈ (0+1)* I no(s)-n1(s) I ≤ 4
(20) Which one of the following statement is false?
(A) In Chomsky Normal Form the derivative trees of strings generated by a context-free grammar are always binary trees
(B) If W is the string of a terminals and Y is a non-terminal, the language generated by a context free grammar, all of whose productions are of the form x->W or X->WY is always regular
(C) By using suitable transformation all ε-productions can be removed from any context-free grammar.
(D) Every left recursive grammar can be converted to a right recursive grammar and vice-versa
ANSWER: If W is the string of a terminals and Y is a non-terminal, the language generated by a context free grammar, all of whose productions are of the form x->W or X->WY is
always regular