1
GATE CSE 2012
+2
-0.6
Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zeros. For example, $$001110$$ and $$011001$$ are in the language, but $$100010$$ is not. All strings of length less than $$3$$ are also in the language. A partially completed $$DFA$$ that accepts this language is shown below.

The missing arcs in the $$DFA$$ are A B C D 2
GATE CSE 2011
+2
-0.6
Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \right.\left| {k > 0,\,n} \right.$$ is a positive integer constant$$\left. \, \right\}$$

What is the minimum number of states needed in a $$DFA$$ to recognize $$L$$?

A
$$k+1$$
B
$$n+1$$
C
$${2^{n + 1}}$$
D
$${2^{k + 1}}$$
3
GATE CSE 2010
+2
-0.6
Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is the set of all bit strings with even number of $$1's.$$ which one of rhe regular expression below represents $$L.$$
A
$$\left( {{0^ * }{{10}^ * }1} \right){}^ *$$
B
$${0^ * }\left( {{{10}^ * }{{10}^ * }} \right){}^ *$$
C
$${0^ * }\left( {{{10}^ * }1} \right){}^ * {0^ * }$$
D
$${0^ * }\,\,1\left( {{{10}^ * }1} \right){}^ * {10^ * }$$
4
GATE CSE 2010
+2
-0.6
Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum number of states in a non-deterministic finite automation that accepts $$L$$?
A
$$n-1$$
B
$$n$$
C
$$n+1$$
D
$${2^{n + 1}}$$
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
EXAM MAP
Joint Entrance Examination