|
1476
|
1 |
(* Title: HOL/Lex/Auto.thy
|
|
1344
|
2 |
ID: $Id$
|
|
1476
|
3 |
Author: Tobias Nipkow
|
|
1344
|
4 |
Copyright 1995 TUM
|
|
|
5 |
|
|
|
6 |
Automata expressed as triples of
|
|
|
7 |
1. a start state,
|
|
|
8 |
2. a transition function and
|
|
|
9 |
3. a test for final states.
|
|
|
10 |
|
|
|
11 |
NOTE: this functional representation is suitable for all kinds of automata,
|
|
|
12 |
not just finite ones!
|
|
|
13 |
*)
|
|
|
14 |
|
|
|
15 |
Auto = Prefix +
|
|
|
16 |
|
|
|
17 |
types ('a,'b)auto = "'b * ('b => 'a => 'b) * ('b => bool)"
|
|
|
18 |
|
|
1559
|
19 |
constdefs
|
|
|
20 |
|
|
1374
|
21 |
start :: ('a, 'b)auto => 'b
|
|
1559
|
22 |
"start(A) == fst(A)"
|
|
|
23 |
|
|
1374
|
24 |
next :: ('a, 'b)auto => ('b => 'a => 'b)
|
|
1559
|
25 |
"next(A) == fst(snd(A))"
|
|
1344
|
26 |
|
|
1559
|
27 |
fin :: ('a, 'b)auto => ('b => bool)
|
|
|
28 |
"fin(A) == snd(snd(A))"
|
|
|
29 |
|
|
|
30 |
nexts :: ('a, 'b)auto => 'b => 'a list => 'b
|
|
|
31 |
"nexts(A) == foldl(next(A))"
|
|
1344
|
32 |
|
|
1559
|
33 |
accepts :: ('a,'b) auto => 'a list => bool
|
|
|
34 |
"accepts A xs == fin A (nexts A (start A) xs)"
|
|
1344
|
35 |
|
|
1559
|
36 |
acc_prefix :: ('a, 'b)auto => 'b => 'a list => bool
|
|
|
37 |
"acc_prefix A st xs == ? us. us <= xs & us~=[] & fin A (nexts A st us)"
|
|
1344
|
38 |
|
|
|
39 |
end
|