1
GATE CSE 2007
+2
-0.6
Consider the following finite state automation The minimum state automation equivalent to the above $$FSA$$ has the following number of states

A
$$1$$
B
$$2$$
C
$$3$$
D
$$4$$
2
GATE CSE 2006
+2
-0.6
If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left( s \right)$$ the number of $$1'$$s in $$s.$$ Which one of the following languages is not regular?
A
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {{n_0}\left( s \right)\,\,} \right.} \right.$$ is a $$3$$-digit prime$$\left. \, \right\}$$
B
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,\,} \right.} \right.$$ for every prefix $$s'$$ of $$s.$$ $$\,\left| {{n_0}\left( {{s^,}} \right) - {n_1}\left( {{s^,}} \right)\left| { \le \left. 2 \right\}} \right.} \right.$$
C
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^*}\left\| {{n_0}\left( s \right) - {n_1}\left( s \right)\left| { \le \left. 4 \right\}} \right.} \right.} \right.$$
D
$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }} \right.\left| {{n_0}\left( s \right)} \right.$$ mod $$7 = {n_1}\left( s \right)$$ mod $$5 = \left. 0 \right\}$$
3
GATE CSE 2006
+2
-0.6
Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ accepting this language is
A
$$3$$
B
$$5$$
C
$$8$$
D
$$9$$
4
GATE CSE 2005
+2
-0.6
Consider the machine $$M:$$ The language recognized by $$M$$ is: A
$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ every $$a$$ in $$w$$ is followed by exactly two $$\left. {b's} \right\}$$
B
$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ every $$a$$ in $$w$$ is followed by at least two $$\left. {b's} \right\}$$
C
$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ $$w$$ contains the substring $$\,\left. {'abb'\,\,} \right\}\,$$
D
$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ $$w$$ does not contain $$'aa'$$ as a substring$$\left. \, \right\}$$
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