Automata: Compiling State Machines

6.3.90.900

top ← prev up next →

Automata: Compiling State Machines

package: automata-doc

This package provides macros and functions for writing state machines over racket/match patterns (as opposed to concrete characters.)

1 Machines

(require automata/machine)

package: automata-lib

Each of the subsequent macros compile to instances of the machines provided by this module. This is a documented feature of the modules, so these functions should be used to, for example, determine if the machine is currently accepting.

procedure
(machine? x) → boolean?
x : any/c

Identifies machines.

procedure
(machine guts next) → machine?
guts : any/c
next : (-> any/c machine?)

Constructs a machine.

procedure
(machine-accepting? x) → boolean?
x : any/c

Identifies accepting machines.

procedure
(machine-accepting guts next) → machine?
guts : any/c
next : (-> any/c machine?)

Constructs an accepting machine.

procedure
(machine-accepts? m i) → boolean?
m : machine?
i : (listof any/c)

Returns #t if m ends in an accepting state after consuming every element of i.

procedure
(machine-accepts?/prefix-closed m i) → boolean?
m : machine?
i : (listof any/c)

Returns #t if m stays in an accepting state during the consumption of every element of i.

value
machine-null : machine?

A machine that is never accepting.

value
machine-epsilon : machine?

A machine that is initially accepting and never accepting afterwards.

value
machine-sigma* : machine?

A machine that is always accepting.

procedure
(machine-complement m) → machine?
m : machine?

A machine that inverts the acception criteria of m.

procedure
(machine-star m) → machine?
m : machine?

A machine that simulates the Kleene star of m. m may be invoked many times.

procedure
(machine-union m0 m1) → machine?
m0 : machine?
m1 : machine?

A machine that simulates the union of m0 and m1.

procedure
(machine-intersect m0 m1) → machine?
m0 : machine?
m1 : machine?

A machine that simulates the intersection of m0 and m1.

procedure
(machine-seq m0 m1) → machine?
m0 : machine?
m1 : machine?

A machine that simulates the sequencing of m0 and m1. m1 may be invoked many times.

procedure
(machine-seq* m0 make-m1) → machine?
m0 : machine?
make-m1 : (-> machine?)

A machine that simulates the sequencing of m0 and (make-m1). (make-m1) may be invoked many times.

2 Deterministic Finite Automata

(require automata/dfa)

package: automata-lib

This module provides a macro for deterministic finite automata.

syntax
(dfa start
     (end ...)
     [state ([evt next-state]
             ...)]
     ...)

   start : identifier?
   end : identifier?
   state : identifier?
   next-state : identifier?

A machine that starts in state start where each state behaves as specified in the rules. If a state is in (end ...), then it is constructed with machine-accepting. next-state need not be a state from this DFA.

Examples:

(define M
  (dfa s1 (s1)
       [s1 ([0 s2]
            [(? even?) s1])]
       [s2 ([0 s1]
            [(? even?) s2])]))

> (machine-accepts? M (list 2 0 4 0 2))
#t
> (machine-accepts? M (list 0 4 0 2 0))
#f
> (machine-accepts? M (list 2 0 2 2 0 8))
#t
> (machine-accepts? M (list 0 2 0 0 10 0))
#t
> (machine-accepts? M (list))
#t
> (machine-accepts? M (list 4 0))
#f

3 Non-Deterministic Finite Automata

(require automata/nfa)

package: automata-lib

This module provides a macro for non-deterministic finite automata.

syntax
(nfa (start:id ...)
     (end:id ...)
     [state:id ([evt:expr (next-state:id ...)]
                ...)]
     ...)

   start : identifier?
   end : identifier?
   state : identifier?
   next-state : identifier?

A machine that starts in state (set start ...) where each state behaves as specified in the rules. If a state is in (end ...), then the machine is accepting. next-state must be a state from this NFA.

These machines are efficiently compiled to use the smallest possible bit-string as a set representation and unsafe numeric operations where appropriate for inspection and adjusting the sets.

Examples:

(define M
  (nfa (s1 s3) (s1 s3)
       [s1 ([0 (s2)]
            [1 (s1)])]
       [s2 ([0 (s1)]
            [1 (s2)])]
       [s3 ([0 (s3)]
            [1 (s4)])]
       [s4 ([0 (s4)]
            [1 (s3)])]))

> (machine-accepts? M (list 1 0 1 0 1))
#t
> (machine-accepts? M (list 0 1 0 1 0))
#t
> (machine-accepts? M (list 1 0 1 1 0 1))
#t
> (machine-accepts? M (list 0 1 0 0 1 0))
#t
> (machine-accepts? M (list))
#t
> (machine-accepts? M (list 1 0))
#f

4 Non-Deterministic Finite Automata (with epsilon transitions)

(require automata/nfa-ep)

package: automata-lib

This module provides a macro for non-deterministic finite automata with epsilon transitions.

syntax
epsilon

A binding for use in epsilon transitions.

syntax
(nfa/ep (start:id ...)
        (end:id ...)
        [state:id ([epsilon (epsilon-state:id ...)]
                   ...
                   [evt:expr (next-state:id ...)]
                   ...)]
        ...)

   start : identifier?
   end : identifier?
   state : identifier?
   epsilon-state : identifier?
   next-state : identifier?

Extends nfa with epsilon transitions, which must be listed first for each state.

Examples:

(define M
  (nfa/ep (s0) (s1 s3)
          [s0 ([epsilon (s1)]
               [epsilon (s3)])]
          [s1 ([0 (s2)]
               [1 (s1)])]
          [s2 ([0 (s1)]
               [1 (s2)])]
          [s3 ([0 (s3)]
               [1 (s4)])]
          [s4 ([0 (s4)]
               [1 (s3)])]))

> (machine-accepts? M (list 1 0 1 0 1))
#t
> (machine-accepts? M (list 0 1 0 1 0))
#t
> (machine-accepts? M (list 1 0 1 1 0 1))
#t
> (machine-accepts? M (list 0 1 0 0 1 0))
#t
> (machine-accepts? M (list))
#t
> (machine-accepts? M (list 1 0))
#f

5 Regular Expressions

(require automata/re)

package: automata-lib

This module provides a macro for regular expression compilation.

syntax
(re re-pat)

re-pat = (rec id re-pat)
| ,expr
| (complement re-pat)
| (seq re-pat ...)
| (union re-pat ...)
| (star re-pat)
| epsilon
| nullset
| re-transformer
| (re-transformer . datum)
| (dseq pat re-pat)
| pat

Compiles a regular expression over match patterns to a machine.

The interpretation of the pattern language is mostly intuitive. The pattern language may be extended with define-re-transformer. dseq allows bindings of the match pattern to be used in the rest of the regular expression. (Thus, they are not really regular expressions.) unquote escapes to Racket to evaluate an expression that evaluates to a regular expression (this happens once, at compile time.) rec binds a Racket identifier to a delayed version of the inner expression; even if the expression is initially accepting, this delayed version is never accepting.

The compiler will use an NFA, provided complement and dseq are not used. Otherwise, many NFAs connected with the machine simulation functions from automata/machine are used.

syntax
complement
syntax
seq
syntax
union
syntax
star
syntax
epsilon
syntax
nullset
syntax
dseq
syntax
rec

Bindings for use in re.

syntax
(define-re-transformer id expr)

Binds id as an regular expression transformer used by the re macro. The expression should evaluate to a function that accepts a syntax object and returns a syntax object that uses the regular expression pattern language.

5.1 Extensions

(require automata/re-ext)

package: automata-lib

This module provides a few transformers that extend the syntax of regular expression patterns.

syntax
(opt re-pat)

Optionally matches re-pat.

syntax
(plus re-pat)

Matches one or more re-pat in sequence.

syntax
(rep re-pat num)

Matches re-pat in sequence num times, where num must be syntactically a number.

syntax
(difference re-pat_0 re-pat_1)

Matches everything that re-pat_0 does, except what re-pat_1 matches.

syntax
(intersection re-pat_0 re-pat_1)

Matches the intersection of re-pat_0 and re-pat_1.

syntax
(seq/close re-pat ...)

Matches the prefix closure of the sequence (seq re-pat ...).

5.2 Examples

Examples:

> (define-syntax-rule (test-re R (succ ...) (fail ...))
    (let ([r (re R)])
      (printf "Success: ~v => ~v\n" succ (machine-accepts? r succ))
      ...
      (printf "Failure: ~v => ~v\n" fail (machine-accepts? r fail))
      ...))
> (test-re epsilon
            [(list)]
            [(list 0)])
Success: '() => #t
Failure: '(0) => #f
> (test-re nullset
           []
           [(list) (list 1)])
Failure: '() => #f
Failure: '(1) => #f
> (test-re "A"
           [(list "A")]
           [(list)
            (list "B")])
Success: '("A") => #t
Failure: '() => #f
Failure: '("B") => #f
> (test-re (complement "A")
           [(list)
            (list "B")
            (list "A" "A")]
           [(list "A")])
Success: '() => #t
Success: '("B") => #t
Success: '("A" "A") => #t
Failure: '("A") => #f
> (test-re (union 0 1)
           [(list 1)
            (list 0)]
           [(list)
            (list 0 1)
            (list 0 1 1)])
Success: '(1) => #t
Success: '(0) => #t
Failure: '() => #f
Failure: '(0 1) => #f
Failure: '(0 1 1) => #f
> (test-re (seq 0 1)
           [(list 0 1)]
           [(list)
            (list 0)
            (list 0 1 1)])
Success: '(0 1) => #t
Failure: '() => #f
Failure: '(0) => #f
Failure: '(0 1 1) => #f
> (test-re (star 0)
           [(list)
            (list 0)
            (list 0 0)]
           [(list 1)])
Success: '() => #t
Success: '(0) => #t
Success: '(0 0) => #t
Failure: '(1) => #f
> (test-re (opt "A")
           [(list)
            (list "A")]
           [(list "B")])
Success: '() => #t
Success: '("A") => #t
Failure: '("B") => #f
> (define-re-transformer my-opt
    (syntax-rules ()
      [(_ pat)
       (union epsilon pat)]))
> (test-re (my-opt "A")
           [(list)
            (list "A")]
           [(list "B")])
Success: '() => #t
Success: '("A") => #t
Failure: '("B") => #f
> (test-re (plus "A")
           [(list "A")
            (list "A" "A")]
           [(list)])
Success: '("A") => #t
Success: '("A" "A") => #t
Failure: '() => #f
> (test-re (rep "A" 3)
           [(list "A" "A" "A")]
           [(list)
            (list "A")
            (list "A" "A")])
Success: '("A" "A" "A") => #t
Failure: '() => #f
Failure: '("A") => #f
Failure: '("A" "A") => #f
> (test-re (difference (? even?) 2)
           [(list 4)
            (list 6)]
           [(list 3)
            (list 2)])
Success: '(4) => #t
Success: '(6) => #t
Failure: '(3) => #f
Failure: '(2) => #f
> (test-re (intersection (? even?) 2)
           [(list 2)]
           [(list 1)
            (list 4)])
Success: '(2) => #t
Failure: '(1) => #f
Failure: '(4) => #f
> (test-re (complement (seq "A" (opt "B")))
           [(list "A" "B" "C")]
           [(list "A")
            (list "A" "B")])
Success: '("A" "B" "C") => #t
Failure: '("A") => #f
Failure: '("A" "B") => #f
> (test-re (seq epsilon 1)
           [(list 1)]
           [(list 0)
            (list)])
Success: '(1) => #t
Failure: '(0) => #f
Failure: '() => #f
> (test-re (seq 1 epsilon)
           [(list 1)]
           [(list 0)
            (list)])
Success: '(1) => #t
Failure: '(0) => #f
Failure: '() => #f
> (test-re (seq epsilon
                (union (seq (star 1) (star (seq 0 (star 1) 0 (star 1))))
                       (seq (star 0) (star (seq 1 (star 0) 1 (star 0)))))
                epsilon)
           [(list 1 0 1 0 1)
            (list 0 1 0 1 0)
            (list 1 0 1 1 0 1)
            (list 0 1 0 0 1 0)
            (list)]
           [(list 1 0)])
Success: '(1 0 1 0 1) => #t
Success: '(0 1 0 1 0) => #t
Success: '(1 0 1 1 0 1) => #t
Success: '(0 1 0 0 1 0) => #t
Success: '() => #t
Failure: '(1 0) => #f
> (test-re (star (complement 1))
           [(list 0 2 3 4)
            (list)
            (list 2)
            (list 234 5 9 1 9 0)
            (list 1 0)
            (list 0 1)]
           [(list 1)])
Success: '(0 2 3 4) => #t
Success: '() => #t
Success: '(2) => #t
Success: '(234 5 9 1 9 0) => #t
Success: '(1 0) => #t
Success: '(0 1) => #t
Failure: '(1) => #f
> (test-re (dseq x (? (curry equal? x)))
           [(list 0 0)
            (list 1 1)]
           [(list)
            (list 1)
            (list 1 0)])
Success: '(0 0) => #t
Success: '(1 1) => #t
Failure: '() => #f
Failure: '(1) => #f
Failure: '(1 0) => #f

top ← prev up next →

1	Machines
2	Deterministic Finite Automata
3	Non-Deterministic Finite Automata
4	Non-Deterministic Finite Automata (with epsilon transitions)
5	Regular Expressions