author | nipkow |
Mon, 17 Aug 1998 11:00:57 +0200 | |
changeset 5323 | 028e00595280 |
parent 5184 | 9b8547a9496a |
child 5608 | a82a038a3e7a |
permissions | -rw-r--r-- |
4832 | 1 |
(* Title: HOL/Lex/NA.thy |
2 |
ID: $Id$ |
|
3 |
Author: Tobias Nipkow |
|
4 |
Copyright 1998 TUM |
|
5 |
||
6 |
Nondeterministic automata |
|
7 |
*) |
|
8 |
||
9 |
NA = List + AutoProj + |
|
10 |
||
11 |
types ('a,'s)na = "'s * ('a => 's => 's set) * ('s => bool)" |
|
12 |
||
13 |
consts delta :: "('a,'s)na => 'a list => 's => 's set" |
|
5184 | 14 |
primrec |
4832 | 15 |
"delta A [] p = {p}" |
4907
0eb6730de30f
Reshuffeling, renaming and a few simple corollaries.
nipkow
parents:
4832
diff
changeset
|
16 |
"delta A (a#w) p = Union(delta A w `` next A a p)" |
4832 | 17 |
|
18 |
constdefs |
|
19 |
accepts :: ('a,'s)na => 'a list => bool |
|
20 |
"accepts A w == ? q : delta A w (start A). fin A q" |
|
21 |
||
5323 | 22 |
constdefs |
23 |
step :: "('a,'s)na => 'a => ('s * 's)set" |
|
24 |
"step A a == {(p,q) . q : next A a p}" |
|
25 |
||
26 |
consts steps :: "('a,'s)na => 'a list => ('s * 's)set" |
|
27 |
primrec |
|
28 |
"steps A [] = id" |
|
29 |
"steps A (a#w) = steps A w O step A a" |
|
30 |
||
4832 | 31 |
end |