101.  Which of the following languages are contextfree?
L1 = {a^m b^n a^n b^m ⎪ m, n ≥ 1} L2 = {a^m b^n a^m b^n ⎪ m, n ≥ 1} L3 = {a^m b^n ⎪ m = 2n + 1} 
a.  L1 and L2 only 
b.  L1 and L3 only 
c.  L2 and L3 only 
d.  L3 only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).L1 and L3 only

102.  Which one of the following statements is FALSE ? 
a.  There exist contextfree languages such that all the contextfree grammars generating them are ambiguous 
b.  An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it 
c.  Both deterministic and nondeterministic pushdown automata always accept the same set of languages 
d.  A finite set of string from one alphabet is always a regular language 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Both deterministic and nondeterministic pushdown automata always accept the same set of languages

103.  If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations. 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! 
Answer: (d).D

104.  Consider the following contextfree grammars. Which one of the following pairs of languages is generated by G1 and G2, respectively. 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).D

105.  Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottomofstack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.
(s, a, Z0) → (s, XXZ0) (s, ϵ, Z0) → (f, ϵ) (s, a, X) → (s, XXX) (s, b, X) → (t, ϵ) (t, b, X) → (t,.ϵ) (t, c, X) → (u, ϵ) (u, c, X) → (u, ϵ) (u, ϵ, Z0) → (f, ϵ) The language accepted by the PDA is 
a.  {a^lb^mc^n  l = m = n} 
b.  {a^lb^mc^n  l = m} 
c.  {a^lb^mc^n  2l = m+n} 
d.  {a^lb^mc^n  m=n} 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).{a^lb^mc^n  2l = m+n}

106.  A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S→aS∣A A→aAb∣bAa∣ϵ Which of the following strings is generated by the grammar above? 
a.  aabbaba 
b.  aabaaba 
c.  abababb 
d.  aabbaab 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).aabbaab

107.  Consider 2 scenarios:
C1: For DFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* C2: For NFA (ϕ, Ʃ, δ, qo, F), if F = ϕ, then L = Ʃ* Where F = Final states set ϕ = Total states set Choose the correct option ? 
a.  Both are true 
b.  Both are False 
c.  C1 is true, C2 is false 
d.  C1 is false, C2 is true 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).C1 is true, C2 is false

108.  Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG ‘G’ and given string ‘w’, what is the relation between l , P , r ? 
a.  l ≤ P ≥ r 
b.  l = P = r 
c.  l ≥ P ≤ r 
d.  none of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).l = P = r

109.  Which of the following statements is/are FALSE?
1. For every nondeterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection. 
a.  1 and 4 only 
b.  1 and 3 only 
c.  2 only 
d.  3 only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).2 only

110.  Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
(A) L2 – L1 is recursively enumerable. (B) L1 – L3 is recursively enumerable (C) L2 ∩ L1 is recursively enumerable (D) L2 ∪ L1 is recursively enumerable. 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).B
