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!

Java Programming

Level up your coding skills with our Java Programming MCQs. From object-oriented...

Management Information Systems

Discover how businesses leverage technology with our Management Information Systems...

Operating System

Dive deep into the core of computers with our Operating System MCQs. Learn about...

Data Science

Discover the fascinating world of extracting insights from data with our Data Science...

Microprocessor

Understand the heart of your computer with our Microprocessor MCQs. Topics include...

Formal Languages and Automata Theory

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

CSS

Polish your web design skills with our CSS MCQs. Learn about selectors, properties,...

MySQL Database

Enhance your knowledge of relational databases with our MySQL MCQs. Understand...

Internet of Things (IoT)

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