Q41. If the strings of a language L ={<M>| M is an encoding of turing machines
that have more than 34567890 states}, can be effectively enumerated in
lexicographic (i.e. alphabetic) order, which of the following statements is
true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free
Q42. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aSb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q43. Let G=({S},{a,b,c},R,S) be a context-free grammar where the rule set is
S� aSa|bSb|c.
Which of the following statements is true?
a) G is ambiguous
b) There exist x and y in L(G) such that xy is in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q44. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aSb|SSSSSSSSSSS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q45. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aSb|aaSbb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q46. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aaSbb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q47. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aaaSbbb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q48. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� abSba|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q49. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aaabaaaSbbbabbb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) There exist a deterministic push down automaton that accepts L(G)
d) We can find a deterministic finite state automaton that accepts L(G)
Q50. Choose the correct statement for the language L={a^nb^n|n>=0}
a) L is inherently ambiguous
b) L is deterministic context-free
c) L is regular
d) There exists a deterministic two way finite automata accepting L
Q51. Choose the correct statement for the language L={a^100nb^100n|n>=0}
a) L is inherently ambiguous
b) L is deterministic context-free
c) L is regular
d) There exists a deterministic two way finite automata accepting L
Q52. Choose the correct statement for the language
L={(aaabaaa)^1000n(bbbbbbb)^34567n|n>=0}
a) L is inherently ambiguous
b) L is deterministic context-free
c) L is regular
d) There exists a deterministic two way finite automata accepting L
Q53. Choose the correct statement for the language L={"("^n " )" ^n|n>=0}
a) L is inherently ambiguous
b) L is deterministic context-free
c) L is regular
d) There exists a deterministic two way finite automata accepting L
Q54. Choose the correct statement for the language L={(begin)^n(end)^n|n>=0}
a) L is inherently ambiguous
b) L is deterministic context-free
c) L is regular
d) There exists a deterministic two way finite automata accepting L
Q55. Let G=({S},{a,b},R,S) be a context-free grammar where the rule set is
S� aSb|SS|e
Which of the following statements is true?
a) G is not ambiguous
b) There exist x and y in L(G) such that xy is not in L(G)
c) L(G) is the set of all strings of balanced parenthesis with a as the opening
parenthesis and b as the closing parenthesis.
d) We can find a deterministic finite state automaton that accepts L(G)
Q56. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a
polynomial time computable bijection such that (� x)[xe L2]. Further, let f^-1
be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 finite
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is recursive
Q57. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a
polynomial time computable bijection such that (� x)[xe L2]. Further, let f^-1
be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 finite
b) L1e NP and L2e P-SPACE
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is context-sensitive
Q58. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a
polynomial time computable bijection such that (� x)[xe L2]. Further, let f^-1
be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 regular
b) L1e NP and L2e P
c) L1 is undecidable and L2 is decidable
d) L1 is context-sensitive and L2 is recursive
Q59. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a
polynomial time computable bijection such that (� x)[xe L2]. Further, let f^-1
be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P-SPACE and L2 e DSPACE(n^1000)
b) L1e NP and L2e DTIME(2^1000n)
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is accepted by a 2PDA
Q60. Consider two languages L1 and L2 each on the alphabet S . Let f: S ->S be a
polynomial time computable bijection such that (� x)[xe L2]. Further, let f^-1
be also polynomial time computable.
Which of the following CANNOT be true?
a) L1 e P and L2 is accepted by a 2NFA
b) L1e NP and L2is accepted by a linear bounded automata
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is accepted by a turing machine that
halts on all inputs
