THEORY OF COMPUTATION 3
THEORY OF COMPUTATION 3
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 contextfree grammar where the rule set is Sà aSbSSe 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 contextfree grammar where the rule set is Sà aSabSbc. 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 contextfree grammar where the rule set is Sà aSbSSSSSSSSSSSe 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 contextfree grammar where the rule set is Sà aSbaaSbbSSe 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 contextfree grammar where the rule set is Sà aaSbbSSe 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 contextfree grammar where the rule set is Sà aaaSbbbSSe 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 contextfree grammar where the rule set is Sà abSbaSSe 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 contextfree grammar where the rule set is Sà aaabaaaSbbbabbbSSe 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^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
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^100nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
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)^34567nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
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 " )" ^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
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)^nn>=0}
a) L is inherently ambiguous
b) L is deterministic contextfree
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 contextfree grammar where the rule set is Sà aSbSSe 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 PSPACE
c) L1 is undecidable and L2 is decidable
d) L1 is recursively enumerable and L2 is contextsensitive
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 contextsensitive 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 PSPACE 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
