+1 vote
41 views
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?
| 41 views
0

@Shreya2002

$1188\ ?$

0

How?

0
0
0

@toxicdesire

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.

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

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

+1

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

Yes you are right Thank you:)