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





Related Posts

    Tags


    #

    Current Affairs
    ♦ PRAGATI प्‍लेटफार्म एक _____________ स्तरीय प्रणाली है। » 3
    ♦ अंतर्राष्ट्रीय शिक्षा दिवस कब मनाया गया? » 24 जनवरी
    ♦ अंतर्राष्ट्रीय शिक्षा दिवस कब घोषित किया गया था? » 3 दिसंबर, 2018
    ♦ भारत-पाकिस्तान युद्ध कब स्थापित किया गया था? » 1965
    ♦ शिक्षा का अधिकार भारतीय संविधान के ____________ में डाला गया था » अनुच्छेद 21-ए
    ♦ ऑपरेशन शरद हवा कब खत्म हुआ? » 27 जनवरी, 2021
    ♦ शिक्षा का अधिकार ____________ आयु वर्ग के बच्चों के लिए एक बुनियादी अधिकार है। » 6 से 14
    ♦ मानव अधिकारों की सार्वभौमिक घोषणा के ____________ में शिक्षा का अधिकार शामिल है। » अनुच्छेद 26
    ♦ पेरियार टाइगर रिजर्व कहाँ स्थित है? » केरला
    ♦ नवंबर 2020 तक, भारत की स्थापित सौर ऊर्जा क्षमता ____________ है » 36.9 GW