dfa/README at master · cathoderay/dfa · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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.