DETERMINISTIC FINITE AUTOMATON (A BIT OF THEORY)
===============================================
Formal definition:
------------------
M : (Q, Σ, δ, q0, F)
Q finite set of internal states
Σ finite set of symbols -- input alphabet
δ : Q x Σ -> Q total function -- transition function
q0 ∈ Q initial state
F ⊆ Q set of terminal states
How a DFA operates:
-------------------
For each symbol in an input string, the automaton applies the δ function.
If the string is processed as a whole and reaches a terminal state, then the
string is considered accepted. Otherwise, it is rejected.
A better way to understand/visualize automaton operations is to draw a graph
from its definition.
For example, an automaton that processes the language
L = {a^nb : n >= 0},
can be represented by the following graph:
____ ____ ____
----> | | b | * | a, b | |
| q0 |---------->| q1 |---------->| q2 |<-----+
+->|____| |____| |____| |
| | | | a, b
|_____| |________|
a
* is a terminal state.
TRANSLATING TO PYTHON
=====================
Translating to Python syntax (previous example):
S (alphabet) : list of valid symbols (input alphabet), e.g.
["a", "b"]
Q (states) : list of internal states, e.g.
["q0", "q1", "q2"]
q0 (initial) : an element from Q, e.g.
"q0"
F (terminals) : list of final states, e.g.
["q1"]
D (delta) : dictionary that represents the transitions from
the state machine, e.g.
{("q0", "a") : "q0",
("q0", "b") : "q1",
("q1", "a") : "q2",
("q1", "b") : "q2",
("q2", "a") : "q2",
("q2", "b") : "q2"}
CREATING YOUR AUTOMATON
=======================
See examples in the automata directory.
CHECKING YOUR AUTOMATON
=======================
$ ./check automata/one_zero.yaml
String: 001
001 is rejected.
String: 110
110 is accepted.
HOW TO USE AS A MODULE
======================
See example.py.