Awesome q2a theme
+1 vote
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?
in Theory of Computation by (7 points) | 41 views


$1188\ ?$

Is the answer correct ?


I was just thinking if I can get an assurity about the answer, then I can explain in detail :) as I have gone through these types of questions but not exactly this one. It is a good question.

I haven't seen anything like it before, so I'm getting something far off, I might just be very very wrong.

But I can't figure out where.

For each vertex, there are $4$ choices for picking $a$'s transitions, $4$ choices for picking $b$'s transitions, and there are $4$ such vertices.

And all states should be non-final in order reject every possible string in the language including $\epsilon$.

So, my answer gives $4^3  = 64$

Since designated initial state given then initial state has to be fix 

If there are three states X,Y,Z and if we make X as initial state then we are not going to change it throughout the process because designated initial state given in the question and we know ⋵ is not empty language It is empty string So here we can't make X as final state because it's already initial state so that if we make X as final state then our DFA is going to accept empty string (means atleast one string ) So our DFA not able to accept empty language that's why we don't make X as the final state because by doing this our DFA can't able to accept empty language

Here one thing that we need to keep in mind is that if there is no final state then whatever transition we write DFA can't accept anything means DFA accept empty language that we want and If there is atleast one final state then our DFA can able to accept empty language only if final state is not reachable from initial state

Thank you @ for solving this problem


Are you sure about this ?

No final state$=729 \checkmark$

Two final state$=81 \checkmark$

For One final state, let's take $Y,$ I am getting$=189$ 

For One final state, let's take $Z,$ I am getting$=189$ 



Yes you are right Thank you:)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jun 2020
  1. vps123

    4 Points

  2. ummokkate

    1 Points

  3. Kushagra गुप्ता

    1 Points

  4. faseela45

    1 Points

  5. srestha

    1 Points

7,385 questions
1,744 answers
90,357 users