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

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}
Discuss
Answer: (b).L1 and L3 only
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.

a.

A

b.

B

c.

C

d.

D

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.

a.

A

b.

B

c.

C

d.

D

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
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?
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 ?
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 ?
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.
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.

a.

A

b.

B

c.

C

d.

D

Discuss
Answer: (b).B

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!