The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
In DFA, does each state need to have transition on "EACH" input alphabet?

The answer was given "False" but I dont think so. Can anyone explain?

Because if this statement is False, then there is no use of "Dead State"
asked in Theory of Computation by Junior (507 points) | 54 views
i think it should be true.In DFA any state has transition for all input symbols.
@Subham Nagar,Only a single transition for a given alphabet. If there is more than one transition,in that case it's an NFA.:). Please correct me if I am wrong.

@Devshree, yes that is evident, but what the concerned doubt over here was that "whether for every state, there should be transition on EACH alphabet". 

For example if $\sum {a,b}$  , then a state Qi should have a defined transition on  both a and b

Yes it should be corect statement.
Made Easy and Ace Academy are known for irrelevant and incorrect solutions as well. The given statement is true.

1 Answer

0 votes
I think its true , if anyone finds counter example then please explain it too.
answered by Junior (627 points)

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

35,518 questions
42,792 answers
42,162 users