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

Explore more Topics under GATE CSE Exam

Q11.
Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

a.

Df ⊂ Nf and Dp ⊂ Np

b.

Df ⊂ Nf and Dp = Np

c.

Df = Nf and Dp = Np

d.

Df = Nf and Dp ⊂ Np

Discuss
Answer: (d).Df = Nf and Dp ⊂ Np
Q12.
The regular expression 0*(10*)* denotes the same set as

a.

(1*0)*1*

b.

0 + (0 + 10)*

c.

(0 + 1)* 10(0 + 1)*

d.

none of these

Discuss
Answer: (d).none of these
Q13.
The smallest finite automation which accepts the language {x | length of x is divisible by 3} has :

a.

2 states

b.

3 states

c.

4 states

d.

5 states

Discuss
Answer: (b).3 states
Q14.
Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

a.

N^2

b.

2^N

c.

2N

d.

N!

Discuss
Answer: (b).2^N
Q15.
Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

a.

8

b.

14

c.

15

d.

48

Discuss
Answer: (d).48
Q16.
Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

a.

S ⊂ T

b.

T ⊂ S

c.

S = T

d.

S ∩ T = φ

Discuss
Answer: (c).S = T
Q17.
Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true?

a.

L = 0+

b.

L is regular but not 0+

c.

L is context free but not regular

d.

L is not context free

Discuss
Answer: (b).L is regular but not 0+
Q18.
What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

a.

L must be {a^n| n is odd}

b.

L must be {a^n| n is even}

c.

L must be {a^n| ³ O}

d.

Either L must be {a^n | n is odd}, or L must be {a^n | n is even}

Discuss
Answer: (d).Either L must be {a^n | n is odd}, or L must be {a^n | n is even}
Q19.
How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's.

a.

1

b.

2

c.

3

d.

4

Discuss
Answer: (b).2
Q20.
Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}

Which one of the following choices precisely represents the strings in X0?

a.

10 (0* + (10)*)1

b.

10 (0* + (10)*)*1

c.

1(0* + 10)*1

d.

10 (0 + 10)*1 + 110 (0 + 10)*1

Discuss
Answer: (c).1(0* + 10)*1
Page 2 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!

Internet of Things (IoT)

Discover how devices communicate with each other in the smart world with our IoT...

Cloud Computing

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

SQL Server

Master Microsoft's database server with our SQL Server MCQs. Topics cover database...

IT Fundamentals

Navigate the basics of information technology with our IT Fundamentals MCQs. Get a...

Systems Programming

Decode low-level programming with our Systems Programming MCQs. These questions delve...

Neural Networks

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

Computer Graphics

Step into the visual side of computing with our Computer Graphics MCQs. Cover topics...

Software Architecture and Design

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

Formal Languages and Automata Theory

Discover the mathematical models of computation with our Formal Languages and...