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!

Object Oriented Programming

Enhance your coding skills with our Object Oriented Programming MCQs. Understand...

Digital Image Processing (DIP)

Delve into the techniques of enhancing digital images with our Digital Image...

MS Office

Master the suite of productivity tools with our MS Office MCQs. From Word and Excel...

Data Science

Discover the fascinating world of extracting insights from data with our Data Science...

Computer Architecture

Unveil the science behind computer design with our Computer Architecture MCQs. Topics...

Software Architecture and Design

Get a strong hold on the blueprint of software systems with our Software Architecture...

UNIX

Become proficient with the Unix operating system using our UNIX MCQs. Learn about...

Wireless and Mobile Communications

Get to grips with modern communication technologies with our Wireless and Mobile...

Python

Dive into one of the most popular languages with our Python MCQs. Understand...