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!

PHP

Venture into server-side scripting with our PHP MCQs. Cover everything from syntax...

Systems Programming

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

MongoDB

Learn the leading NoSQL database with our MongoDB MCQs. Understand everything from...

Hadoop

Dive into the world of big data with our Hadoop MCQs. Cover key concepts including...

C# programming

Hone your skills in the C# language with our MCQs. Understand data types, operators,...

Reverse Engineering

Strengthen your understanding of Reverse Engineering with our curated set of MCQs....

Java Programming

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

Python

Dive into one of the most popular languages with our Python MCQs. Understand...

R Programming

Unleash the power of statistical computing with our R Programming MCQs. Topics cover...