GeezerVison

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.