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 12 of 14

Explore more Topics under GATE CSE Exam

Q111.
Which of the following is true for the language given below:

a.

It is not accepted by a Turing Machine

b.

It is regular but not context-free

c.

It is context-free but not regular

d.

It is neither regular nor context-free, but accepted by a Turing machine

Discuss
Answer: (d).It is neither regular nor context-free, but accepted by a Turing machine
Q112.
If L and L' are recursively enumerable, then L is

a.

regular

b.

context-free

c.

context-sensitive

d.

recursive

Discuss
Answer: (d).recursive
Q113.
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?

a.

Neither L nor L' is recursively enumerable (r.e.)

b.

One of L and L' is r.e. but not recursive; the other is not r.e

c.

Both L and L' are r.e. but not recursive

d.

Both L and L' are recursive

Discuss
Answer: (c).Both L and L' are r.e. but not recursive
Q114.
Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

a.

If A ≤m B and B is recursive then A is recursive

b.

If A ≤m B and A is undecidable then B is undecidable

c.

If A ≤m B and B is recursively enumerable then A is recursively enumerable

d.

If A ≤m B and B is not recursively enumerable then A is not recursively enumerable

Discuss
Answer: (d).If A ≤m B and B is not recursively enumerable then A is not recursively enumerable
Q115.
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?

a.

L is recursively enumerable, but not recursive

b.

L is recursive, but not context-free

c.

L is context-free, but not regular

d.

L is regular

Discuss
Answer: (d).L is regular
Q116.
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

L1' --> Complement of L1
L2' --> Complement of L2

a.

L1' is recursive and L2' is recursively enumer­able

b.

L1' is recursive and L2' is not recursively enumerable

c.

L1' and L2' are recursively enumerable

d.

L1' is recursively enumerable and L2' is recursive

Discuss
Answer: (b).L1' is recursive and L2' is not recursively enumerable
Q117.
A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

 0 1 B
 q0  q1, 1, R q1, 1, R  Halt
 q1  q1, 1, R   q0, 1, L   q0, B, L  

The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?

a.

M does not halt on any string in (0 + 1)+

b.

M does not halt on any string in (00 + 1)*

c.

M halts on all string ending in a 0

d.

M halts on all string ending in a 1

Discuss
Answer: (a).M does not halt on any string in (0 + 1)+
Q118.
For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

1. L1' (complement of L1) is recursive
2. L2' (complement of L2) is recursive
3. L1' is context-free
4. L1' ∪ L2 is recursively enumerable

a.

1 only

b.

3 only

c.

3 and 4 only

d.

1 and 4 only

Discuss
Answer: (d).1 and 4 only
Q119.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y' reduces to W, and Z reduces to X' (reduction means the standard many-one reduction).
Which one of the following statements is TRUE ?

a.

W can be recursively enumerable and Z is recursive

b.

W an be recursive and Z is recursively enumerable

c.

W is not recursively enumerable and Z is recursive

d.

W is not recursively enumerable and Z is not recursive

Discuss
Answer: (c).W is not recursively enumerable and Z is recursive
Q120.
Consider the following types of languages:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable.

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is context-free
IV. L1 U L2' is context-free

a.

I only

b.

I and III only

c.

I and IV only

d.

I, II and III only

Discuss
Answer: (d).I, II and III only
Page 12 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!

Cryptography and Network Security

Secure your knowledge of information security with our Cryptography and Network...

Discrete Mathematics

Refine your mathematical skills essential for computer science with our Discrete...

Systems Analysis and Design Methods

Get familiar with the process of designing and improving business systems with our...

Neural Networks

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

MATLAB

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

Computer Hardware

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

MongoDB

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

Object Oriented Programming

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

Cloud Computing

Stay on top of the biggest trend in IT with our Cloud Computing MCQs. These questions...