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

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

Sà aSb|SS|e

Which of the following statements is true?

Sà aSa|bSb|c.

Which of the following statements is true?

Sà aSb|SSSSSSSSSSS|e

Which of the following statements is true?

Sà aSb|aaSbb|SS|e

Which of the following statements is true?

Sà aaSbb|SS|e

Which of the following statements is true?

Sà aaaSbbb|SS|e

Which of the following statements is true?

Sà abSba|SS|e

Which of the following statements is true?

Sà aaabaaaSbbbabbb|SS|e

Which of the following statements is true?

Sà aSb|SS|e

Which of the following statements is true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

Which of the following CANNOT be true?

## Related Posts

Current Affairs