What are the rules for constructing a deterministic finite automata in the form of a diagram? My professor explained by examples, but I am not exactly sure what rules must be followed by all diagrams. Any help is appreciated, thanks!
Add a comment |
1 Answer
Off the top of my head, in a DFA, these are the main rules, (terms specific to DFAs are in double quotes):-
each "state" must have a "transition" for each "input" defined in the DFA
so this means, that a transition must be defined for every input being considered in a dfa, for a state, so that one knows where to go from that state for each input.each "state" can have only ONE "transition" for each "input"
well this rule is pretty self explanatory, so if you have already defined a transition for an input for a particular state, don't create another transition for the same input from the same state.
Yeah these are the ones i remember. Hope it helps. Further these points can be used to differentiate a dfa from a nfa. Other simple rules for drawing would be :-
make a start state, indicated with arrow pointing towards the state
have at least one final state, indicated with concentric circles to draw the state boundary
draw the transitions as arrows
mark all the transitions with their respective input symbols
16 Comments
tehman
one thing that I was wondering, lets say there was a language consisting of two inputs, {a, b}. Does the starting state have to branch to both a and b? And does each state after that have to have an a and b output or is it just mandatory for the starting point?
bool.dev
let me know if it helped, or if you want a better answer!!
bool.dev
yeah all states need to have branches for each input, start state or any state in between, or the final accepting state
bool.dev
@HQuser, yes, and this is also mentioned in the answer, specifically the first point:
each "state" must have a "transition" for each "input" defined in the DFAbool.dev
@HQuser, i guess you up voted my comment, which is great, but incase my answer helped you, please considering up voting it as well :) Sorry, if you find this impolite.
|