CurrentGK -> Papers -> GAT(Graduate Aptitude Test In Engineering) -> THEORY OF COMPUTATION 3

If you find this context important and usefull. We request to all visitors to sheare this with your friends on social networking channels.

THEORY OF COMPUTATION 3

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 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





Tags


#

11 Dec, 2018, 12:50:48 PM