GATE CSE 2007 | Finite Automata and Regular Language Question 59 | Theory of Computation

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Consider the following finite state automation GATE CSE 2007 Theory of Computation - Finite Automata and Regular Language Question 58 English

The minimum state automation equivalent to the above $$FSA$$ has the following number of states

$$1$$

$$2$$

$$3$$

$$4$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Which of the following languages is regular?

$$\left\{ {w{w^R}} \right.\left| {w \in \left\{ {0,\,1} \right\}\left. {^ + } \right\}} \right.$$

$$\left\{ {w{w^R}} \right.x\left| {x,w \in \left\{ {0,\,1} \right\}\left. {^ + } \right\}} \right.$$

$$\left\{ {wx{w^R}} \right.\left| {x,w \in \left\{ {0,\,1} \right\}\left. {^ + } \right\}} \right.$$

$$\left\{ {xw{w^R}} \right.\left| {x,w \in \left\{ {0,\,1} \right\}\left. {^ + } \right\}} \right.$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,} \right.$$ number of $$0'$$s and $$1'$$s in $$w$$ are divisible by $$3$$ and $$5$$, respectively$$\left. \, \right\}$$ has

$$15$$ states

$$11$$ states

$$10$$ states

$$9$$ states

GATE CSE 2006

MCQ (Single Correct Answer)

-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?

$$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {{n_0}\left( s \right)\,\,} \right.} \right.$$ is a $$3$$-digit prime$$\left. \, \right\}$$

$$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.$$

$$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.$$

$$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\}$$

PREVIOUS NEXT