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.

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

01

Networking

02

Operating System

03

Data Structures and Algorithms

04

Computer Architecture

05

DBMS

06

Compiler Design

07

Engineering Mathematics

Q111.

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

It is not accepted by a Turing Machine

It is regular but not context-free

It is context-free but not regular

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

regular

context-free

context-sensitive

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?

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

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

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

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?

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

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

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

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?

L is recursively enumerable, but not recursive

L is recursive, but not context-free

L is context-free, but not regular

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

L1' is recursive and L2' is recursively enumerable

L1' is recursive and L2' is not recursively enumerable

L1' and L2' are recursively enumerable

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 ?

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

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

M halts on all string ending in a 0

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

1 only

3 only

3 and 4 only

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 ?

W can be recursively enumerable and Z is recursive

W an be recursive and Z is recursively enumerable

W is not recursively enumerable and Z is recursive

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

I only

I and III only

I and IV only

I, II and III only

Discuss

Answer: (d).I, II and III only

Page 12 of 14

Welcome to the Theory of Computation(TOC) MCQs Page

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

Explore more Topics under GATE CSE Exam

Networking

Operating System

Data Structures and Algorithms

Computer Architecture

DBMS

Compiler Design

Engineering Mathematics

Suggested Topics

Software Architecture and Design

Artificial Intelligence

CompTIA PenTest+ Certification Exam PT0 002

Management Information Systems

Embedded Systems

R Programming

Wireless and Mobile Communications

Compiler Design

Java Programming