-
Notifications
You must be signed in to change notification settings - Fork 5
/
renfa.py
117 lines (95 loc) · 3.84 KB
/
renfa.py
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# Copyright 2019-2024, Vincent Hugot <vincent.hugot@insa-cvl.fr>
# This file is part of VH's NFA Framework.
#
# VH's NFA Framework is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
#
# VH's NFA Framework is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
# of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along with VH's NFA Framework.
# If not, see <https://www.gnu.org/licenses/>.
# McNaughton–Yamada–Thompson's algorithm.
# Students: pattern-matching techniques in this file are documented in my lecture notes, sections
# "Advanced structural pattern matching" and "A smidgen of Computer Algebra".
from dataclasses import dataclass
from nfa import *
from functools import cached_property
class _RE: pass
class VOID(_RE): pass
@dataclass
class WRD(_RE): w: str
@dataclass
class BinOp(_RE):
l: object
r: object
class OR (BinOp):
symb = " | "
class CONCAT (BinOp):
symb = ""
@dataclass
class STAR(_RE): e : object
def needsparent(s): return len(s) > 1 and s[0]+s[-1] != "()"
def restr(e):
match e:
case VOID() : return "∅"
case WRD(""): return "ɛ"
case WRD(w) : return w
case BinOp(l,r): return f"({restr(l)}{e.symb}{restr(r)})"
case STAR(e):
s = restr(e)
return f"({s})*" if needsparent(s) else f"{s}*"
case _: raise ValueError(e)
def reaut(e):
match e: # invariant: all states numerical
case VOID() : return NFA({0}, [1], [])
case WRD(""): return NFA({0}, {1}, { (0, "", 1) })
case WRD(w): return NFA.of_word(w)
case OR(l,r):
A,B = NFA.disjoint([reaut(x) for x in (l,r)])
return NFA(["i"], ["f"], {
("i", "", peek(A.I)),
("i", "", peek(B.I)),
(peek(A.F), "", "f"),
(peek(B.F), "", "f") } | A.Δ | B.Δ ).renum()
case CONCAT(l, r):
A, B = NFA.disjoint([reaut(x) for x in (l, r)])
return NFA(["i"], ["f"], {
("i", "", peek(A.I)),
(peek(A.F), "", peek(B.I)),
(peek(B.F), "", "f")} | A.Δ | B.Δ).renum()
case STAR(e):
A = reaut(e)
return NFA(["i"], ["f"], {
("i", "", peek(A.I)), ("i", "", "f"),
(peek(A.F), "", peek(A.I)),
# ("f", "", "i"), # simpler, provided concat is eps, not unify states
(peek(A.F), "", "f")} | A.Δ ).renum()
case _: raise ValueError(e)
class E:
def __init__(s,*args):
match args:
case []: s.e = VOID()
case [str() as x] : s.e = WRD(x)
case [_RE() as x]: s.e = x
case _: assert 0
def __repr__(s):
x = restr(s.e)
return x if len(x) <= 1 or x[0]+x[-1] != "()" else x[1:-1]
def __or__(s, o): return E(OR(s.e,o.e))
def __add__(s,o): return E(CONCAT(s.e,o.e))
def star(s): return E(STAR(s.e))
def MYT(s): return reaut(s.e).named(f"{s}") # McNaughton–Yamada–Thompson
@cached_property
def nfa(s): return s.MYT()
@cached_property
def mini(s): return s.nfa.rm_eps().trim().mini().renum().named(f"{s} /M")
def __contains__(s, w): return w in s.nfa
def __iter__(s): return s.mini.lang()
def __getitem__(s,i): return s.mini.__getitem__(i)
def show(s):
s.nfa.visu() ; s.mini.visu()
return s
def show_all(s):
s.nfa.visu().rm_eps().visu().trim().visu().dfa().visu().mini().visu().renum().visu()
return s