finite state automata
math definition of DFA (deterministic finite automata)
1. Q is a finite set of "states"
2. S is a finite set called the "alphabet"
3. delta : Q x S -> Q is the "transition function"
4. q0 , a member of Q, is the "start state"
5. F , a subset of Q, is the "set of accept states"
programmer's file API
This is a definition of an input file format
that defines a finite state automata, so that
we can write applications that run them and
all be on the same page, so to speak.
The spec has changed substantially since the Jan 24 class,
to keep Josh happy and be consistent with
the YAML spec at
http://yaml.org/spec/current.html .
YAML stands for "YAML Ain't Markup Language";
it's a "data serialization" language that's easy for humans to read
and pretty easy for computers to parse.
# version 0.5
# 1. test files have .fa extensions
# 2. --- at left margin between different docs in the same file
# 3. indentation distinguishes between levels of nesting.
# 4. dashes (-) mark several sequential entities at the same depth
# 5. pound signs (#) at the left mark comments until end of line
# 6. "mappings" are given by " keyword : value "
# 7. a list is given by [ element_1, element_2 ]
# 8. null for NFA's is spelled '~' ; that's part of the YAML spec.
# 9. The "inputs" and "tests" keys are optional.
# a. The "states" and "alphabet" keys are optional;
# if ommitted their values are implied by the transitions.
# Putting all that togeter, a finite automata spec looks like this.
states : [ q0, q1 ]
alphabet : [ 0, 1 ]
start : q0
accept : [ q1 ]
transitions :
# Q x S -> Q
- [ q0, 0, q1 ]
- [ q0, 1, q0 ]
- [ q1, 0, q1 ]
- [ q1, 1, q0 ]
# If we're allowing NFAs (non-deterministic) :
- [ q1, ~, q0 ]
inputs :
- [ 0, 1, 0, 1, 1, 0 ]
- [ 1, 1, 1, 1 ]
- [ ]
tests :
- [ Yes, [0,0,0]]
- [ No, [1,0]]
Even more optional enhancements (to keep Jim happy)
* lists of alpha characters ma be replaced by strings, e.g.
11001 rather than [1,1,0,0,1]
* transitions may specify a list of alpha characters for S, e.g.
[q0, [0,1], q1] to mean "from state q0, either 0 or 1 goes to state q1"
* the letters in the words "Yes" and "No" may be in any case
(I think this is consistent with YAML usage)
