Deterministic finite automata (DFAs)

To insert a sample DFA into your document, select from the editor
Insert⟶ Structure⟶DFA.

A deterministic finite automaton (DFA) is a state machine consisting of 5 components∶
Component
Math notation (example)
Grafstate code
Set of states (Q)
Q={q1,q2,q3}
Q={q1,q2,q3}
Input alphabet (Σ)
Σ={0,1}
S={0,1}
Transition function (δ)
δ(q1,0)=q2
d(q1,0)=q2
Starting state (q0)
q0=q1
q0=q1
Set of final states (F)
F={q2}
F={q2}
To begin the creation of a DFA, enter the command :+ dfa name. The syntax for the DFA code is as follows∶

Syntax constraints for a DFA

Each line of a DFA is checked against the following constraints. If a line violates a constraint, then you will receive an error message.
Q and S must be nonempty sets.
Each state in Q must have exactly one outgoing transition for each symbol in S .
q0 must be defined as an element of Q .
F must be a subset of Q .
Each transition ( d ) has two input parameters. The first paramater is a state (in Q ) and the second parameter is an input symbol (in S ).
The output of each transition must be a state (in Q ).
Q , S , q0 , and F must be defined exactly once.

You may give a DFA an optional title to be displayed on the state diagram using the title instruction. title place a title here .

Example 1

The following is a description of a DFA that recognizes the language of binary strings ending with the symbol 1∶
Code
:+ dfa M1
title example DFA
Q={q1,q2}
S={0,1}
d(q1,0)=q1
d(q1,1)=q2
d(q2,0)=q1
d(q2,1)=q2
q0=q1
F={q2}
done.
The DFA code above produces the following state diagram∶
Deterministic finite automaton
Deterministic finite automaton
M1

The null state

The null state (called 0 ) is a special state that results in a string being rejected, for any string whose computation enters this state. When designing the logic of a DFA, if it is clear that a string should be rejected without needing to read the entire string, then using the null state is a convenient way to force the rejection of the string.

The null state in a DFA (visualized as ∅ in the state diagram) is analogous to the destination of "missing transitions" in an NFA (i.e., transitions to the empty set). The null state is often needed when converting an NFA to an equivalent DFA.

Syntax constraints for the null state

The following syntax constraints are checked when using the null state∶
The name of the null state is 0 , and it must be defined as an element of Q .
The null state cannot be the initial state.
The null state cannot be a final state.
Every transition from the null state must be a self loop.

Example 2 (using the null state)

The following Grafstate code describes a DFA that accepts only the string b. The line d(q1,a)=0 forces the DFA to reject all strings beginning with a. The lines d(q2,a)=0 and d(q2,b)=0 force the DFA to reject all strings of length greater than 1.
Code
:+ dfa M2
title L(M2) = {b}.
Q={q1,q2,0}
S={a,b}
d(q1,a)=0
d(q1,b)=q2
d(q2,a)=0
d(q2,b)=0
d(0,a)=0
d(0,b)=0
q0=q1
F={q2}
done.
Deterministic finite automaton
Deterministic finite automaton
M2

Simulating a DFA

The Grafstate Simulator will show all steps of the computation performed by a DFA M when reading an input string w that you supply. The steps are visualized as a computation sequence. If w is accepted by M, then the computation sequence concludes with a final state qf (belonging to F) inside a solid diamond (i.e., @{ < qf > }). Such a computation sequence is called an accepting sequence. If w is not accepted by M, then the computation sequence concludes with some non-final state q (not in to F) inside a dotted diamond (i.e., @{. < q > }). This kind of computation sequence is called a rejecting sequence.

You can simulate a DFA with the command.
Code
:sim M1 100101
The command above produces the following computation sequence∶
Simulation
Input 100101
Result ACCEPTED
Explanation The following computation path shows all steps of the computation∶
Deterministic finite automaton∶ M1

To simulate a DFA from the menus, right-click on the state diagram and select Simulate.