Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
1
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
The smallest finite automaton which accepts the language
$$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is divisible by $$\left. 3 \right\}$$ has
A
$$2$$ states
B
$$3$$ states
C
$$4$$ states
D
$$5$$ states
2
GATE CSE 2001
MCQ (Single Correct Answer)
+2
-0.6
Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ 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$$
3
GATE CSE 2001
MCQ (Single Correct Answer)
+2
-0.6
Consider the following languages:
$${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right\}$$
$${L_2} = \left\{ {w\,{w^R}\left| {w \in {{\left\{ {a,\,b} \right\}}^ * },} \right.{w^R}\,\,} \right.$$ is the reverse of $$\left. w \right\}$$
$${L_3} = \left\{ {{0^{2i}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$
$${L_4} = \left\{ {{0^{{i^2}}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$

Which of the languages are regular?

A
Only $${L_1}$$ and $${L_2}$$
B
Only $${L_2},$$ $${L_3}$$ and $${L_4}$$
C
Only $${L_3}$$ and $${L_4}$$
D
Only $${L_3}$$
4
GATE CSE 2000
MCQ (Single Correct Answer)
+2
-0.6
What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has two states?
A
Must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is odd $$\left. \, \right\}$$
B
Must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is even $$\left. \, \right\}$$
C
Must be $$\left\{ {{a^n}\left| {n \ge } \right.\,\,} \right.0\left. \, \right\}$$
D
Either $$L$$ must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is odd$$\left. \, \right\}\,\,$$ or $$L$$ must be $$\left\{ {{a^n}\left| n \right.} \right.$$ is even$$\left. \, \right\}$$
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization