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 11 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

Q101.

Which of the following languages are context-free?

L1 = {a^m b^n a^n b^m ⎪ m, n ≥ 1}
L2 = {a^m b^n a^m b^n ⎪ m, n ≥ 1}
L3 = {a^m b^n ⎪ m = 2n + 1}

L1 and L2 only

L1 and L3 only

L2 and L3 only

L3 only

Discuss

Answer: (b).L1 and L3 only

Q102.

Which one of the following statements is FALSE ?

There exist context-free languages such that all the context-free grammars generating them are ambiguous

An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it

Both deterministic and non-deterministic pushdown automata always accept the same set of languages

A finite set of string from one alphabet is always a regular language

Discuss

Answer: (c).Both deterministic and non-deterministic pushdown automata always accept the same set of languages

Q103.

If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations.

Discuss

Answer: (d).D

Q104.

Consider the following context-free grammars. Which one of the following pairs of languages is generated by G1 and G2, respectively.

Discuss

Answer: (d).D

Q105.

Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ)

The language accepted by the PDA is

{a^lb^mc^n | l = m = n}

{a^lb^mc^n | l = m}

{a^lb^mc^n | 2l = m+n}

{a^lb^mc^n | m=n}

Discuss

Answer: (c).{a^lb^mc^n | 2l = m+n}

Q106.

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S→aS∣A
A→aAb∣bAa∣ϵ

Which of the following strings is generated by the grammar above?

aabbaba

aabaaba

abababb

aabbaab

Discuss

Answer: (d).aabbaab

Q107.

Consider 2 scenarios:

C1: For DFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

C2: For NFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

Where F = Final states set
ϕ = Total states set

Choose the correct option ?

Both are true

Both are False

C1 is true, C2 is false

C1 is false, C2 is true

Discuss

Answer: (c).C1 is true, C2 is false

Q108.

Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG ‘G’ and given string ‘w’, what is the relation between l , P , r ?

l ≤ P ≥ r

l = P = r

l ≥ P ≤ r

none of these

Discuss

Answer: (b).l = P = r

Q109.

Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine,
there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union
and complementation.
3. Turing decidable languages are closed under intersection
and complementation.
4. Turing recognizable languages are closed under union
and intersection.

1 and 4 only

1 and 3 only

2 only

3 only

Discuss

Answer: (c).2 only

Q110.

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

(A) L2 – L1 is recursively enumerable.
(B) L1 – L3 is recursively enumerable
(C) L2 ∩ L1 is recursively enumerable
(D) L2 ∪ L1 is recursively enumerable.

Discuss

Answer: (b).B

Page 11 of 14

Welcome to the Theory of Computation(TOC) MCQs Page

Theory of Computation(TOC) MCQs | Page 11 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

MySQL Database

C Programming

Management Information Systems

Compiler Design

JavaScript

Object Oriented Programming Using C++

Computer Hardware

MS Office

Microprocessor