adplus-dvertising

Welcome to the Theory of Computation(TOC) MCQs Page

Dive deep into the fascinating world of Theory of Computation(TOC) with our comprehensive set of Multiple-Choice Questions (MCQs). This page is dedicated to exploring the fundamental concepts and intricacies of Theory of Computation(TOC), a crucial aspect of GATE CSE Exam. In this section, you will encounter a diverse range of MCQs that cover various aspects of Theory of Computation(TOC), from the basic principles to advanced topics. Each question is thoughtfully crafted to challenge your knowledge and deepen your understanding of this critical subcategory within GATE CSE Exam.

frame-decoration

Check out the MCQs below to embark on an enriching journey through Theory of Computation(TOC). Test your knowledge, expand your horizons, and solidify your grasp on this vital area of GATE CSE Exam.

Note: Each MCQ comes with multiple answer choices. Select the most appropriate option and test your understanding of Theory of Computation(TOC). You can click on an option to test your knowledge before viewing the solution for a MCQ. Happy learning!

Theory of Computation(TOC) MCQs | Page 13 of 14

Explore more Topics under GATE CSE Exam

Q121.
Which of the following problems are decidable?

a.

1, 2, 3, 4

b.

1, 2

c.

2, 3, 4

d.

3, 4

Discuss
Answer: (d).3, 4
Q122.
Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

a.

I and II

b.

I and IV

c.

II and III

d.

II and IV

Discuss
Answer: (b).I and IV
Q123.
Which of the following problems is undecidable?

a.

Membership problem for CFGs

b.

Ambiguity problem for CFGs

c.

Finiteness problem for FSAs

d.

Equivalence problem for FSAs

Discuss
Answer: (b).Ambiguity problem for CFGs
Q124.
Let < M > be the encoding of a Turing machine as a string over {0, 1}. Let L = { < M > |M is a Turing machine that accepts a string of length 2014 }. Then, L is

a.

decidable and recursively enumerable

b.

undecidable but recursively enumerable

c.

undecidable and not recursively enumerable

d.

decidable but not recursively enumerable

Discuss
Answer: (b).undecidable but recursively enumerable
Q125.
Which of the following problems is undecidable?

a.

Deciding if a given context-free grammar is ambiguous

b.

Deciding if a given string is generated by a given context-free grammar

c.

Deciding if the language generated by a given context-free grammar is empty

d.

Deciding if the language generated by a given context-free grammar is finite

Discuss
Answer: (a).Deciding if a given context-free grammar is ambiguous
Q126.
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

a.

P3 is decidable if P1 is reducible to P3

b.

P3 is undecidable if P3 is reducible to P2

c.

P3 is undecidable if P2 is reducible to P3

d.

P3 is decidable if P3 is reducible to P2's complement

Discuss
Answer: (c).P3 is undecidable if P2 is reducible to P3
Q127.
Consider the following statements:

1. The complement of every Turning decidable
language is Turning decidable
2. There exists some language which is in NP
but is not Turing decidable
3. If L is a language in NP, L is Turing decidable

Which of the above statements is/are True?

a.

Only 2

b.

Only 3

c.

Only 1 and 2

d.

Only 1 and 3

Discuss
Answer: (d).Only 1 and 3
Q128.
Which of the following decision problems are undecidable ?

a.

I and IV only

b.

II and III only

c.

III and IV only

d.

II and IV only

Discuss
Answer: (c).III and IV only
Q129.
Let L={w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

a.

(0*10*1)*

b.

0*(10*10*)*

c.

0*(10*1*)*0*

d.

0*1(10*1)*10*

Discuss
Answer: (b).0*(10*10*)*
Q130.
Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n|n ∈ N}). Then which of the following is ALWAYS regular?

a.

P ∩ Q

b.

P – Q

c.

∑* – P

d.

∑* – Q

Discuss
Answer: (c).∑* – P
Page 13 of 14

Suggested Topics

Are you eager to expand your knowledge beyond Theory of Computation(TOC)? We've curated a selection of related categories that you might find intriguing.

Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!

MongoDB

Learn the leading NoSQL database with our MongoDB MCQs. Understand everything from...

Microprocessor

Understand the heart of your computer with our Microprocessor MCQs. Topics include...

Computer Hardware

Explore the tangible components of computers with our Computer Hardware MCQs. Learn...

MATLAB

Hone your computational mathematics skills with our MATLAB MCQs. Understand...

CompTIA PenTest+ Certification Exam PT0 002

Prepare for the CompTIA PenTest+ PT0-002 exam with our targeted MCQs. Covering...

Neural Networks

Dive into the world of Artificial Intelligence with our Neural Networks MCQs. Uncover...

Human Computer Interaction

Enhance your knowledge of Human-Computer Interaction with our specialized MCQs....

Management Information Systems

Discover how businesses leverage technology with our Management Information Systems...

Reverse Engineering

Strengthen your understanding of Reverse Engineering with our curated set of MCQs....