Deterministic Finite Automaton, DFA

Idea

• Simplest form of finite automata.
• They are well-behaved in terms of reading all input.

Well-behaved means:

1. For each state in DFA, there is exactly one transition for each letter of the alphabet.
2. There is a unique starting state.

• If 1 or 2 are not met, then it is non-deterministic
• The set of all strings accepted by an automaton is called the language of that automaton.
• If M is an automaton on alphabet ∑ then L(M) is the language of M: