The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
65 views
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 (679 points) | 65 views
+1
i think it should be true.In DFA any state has transition for all input symbols.
0
@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.
0

@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

0
Yes it should be corect statement.
0
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 (657 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

40,927 questions
47,580 answers
146,424 comments
62,311 users