Mescal
Loading...
Searching...
No Matches
nfa_minimization.h
Go to the documentation of this file.
1
9
10#ifndef MINIMIZATION_H
11#define MINIMIZATION_H
12
13 /* _ _ _____ _ __ __ _ _ _ _ _ */
14 /* | \ | | ___/ \ _ | \/ (_)_ __ (_)_ __ ___ (_)______ _| |_(_) ___ _ __ */
15 /* | \| | |_ / _ \ (_) | |\/| | | '_ \| | '_ ` _ \| |_ / _` | __| |/ _ \| '_ \ */
16 /* | |\ | _/ ___ \ _ | | | | | | | | | | | | | | |/ / (_| | |_| | (_) | | | | */
17 /* |_| \_|_|/_/ \_(_) |_| |_|_|_| |_|_|_| |_| |_|_/___\__,_|\__|_|\___/|_| |_| */
18
19
20#include "nfa_determi.h"
21#include "printing.h"
22
23/***************/
24/*+ Auxiliary +*/
25/***************/
26
38dfa* dfa_mini_canonical_copy(dfa*
39);
40
41
42/****************/
43/*+ Brzozowski +*/
44/****************/
45
53dfa* nfa_brzozowski(nfa*
54);
55
56
64dfa* dfa_brzozowski(dfa*
65);
66
67
68/**************/
69/*+ Hopcroft +*/
70/**************/
71
76typedef struct {
77 uint size_set;
78 uint size_par;
79 uint* classes;
80 uint* parray;
81 uint* parray_i;
82 uint* rindex;
83 uint* lindex;
84} hopcroft_partition;
85
86
87
100hopcroft_partition* dfa_hopcroft_initial(uint,
101 uint*,
102 uint
103);
104
112dfa* dfa_hopcroft_genauto(dfa*,
113 hopcroft_partition*
114);
115
120void dfa_hopcroft_free(hopcroft_partition*
121);
122
130dfa* dfa_hopcroft(dfa*
131);
132
133
134/************************/
136/************************/
137
148void dfa_mini_canonical_ordering(dfa*
149);
150
151
152
153#endif
nfa_determi.h
Determinization and complementation of NFAs.
dfa_hopcroft
dfa * dfa_hopcroft(dfa *)
Hopcroft's minimization algorithm.
Definition nfa_minimization.c:209
dfa_brzozowski
dfa * dfa_brzozowski(dfa *)
Brzozowski's minimization algorithm (fo rinput DFAs)
Definition nfa_minimization.c:69
dfa_hopcroft_initial
hopcroft_partition * dfa_hopcroft_initial(uint, uint *, uint)
Computes the initial partition of the states in Hopcroft's algorithm. The set of final states is assu...
Definition nfa_minimization.c:91
dfa_hopcroft_free
void dfa_hopcroft_free(hopcroft_partition *)
Release of a Hopcroft's partition.
Definition nfa_minimization.c:183
dfa_hopcroft_genauto
dfa * dfa_hopcroft_genauto(dfa *, hopcroft_partition *)
Computation of the minimal automaton from the partition computed by the Hopcroft's algorithm.
Definition nfa_minimization.c:138
nfa_brzozowski
dfa * nfa_brzozowski(nfa *)
Brzozowski's minimization algorithm (for input NFAs)
Definition nfa_minimization.c:60
dfa_mini_canonical_ordering
void dfa_mini_canonical_ordering(dfa *)
Computes the canonical ordering of the states of a minimal DFA.
Definition nfa_minimization.c:406
dfa_mini_canonical_copy
dfa * dfa_mini_canonical_copy(dfa *)
Makes a copy of a minimal DFA. The ordering between the states is changed to make the copy canonical.
Definition nfa_minimization.c:7
dfa
Type used to represent a complete DFA.
Definition nfa.h:61
hopcroft_partition
Type used to represent the state partition used in the Hopcroft algorithm.
Definition nfa_minimization.h:76
hopcroft_partition::size_set
uint size_set
The size of the partitioned set.
Definition nfa_minimization.h:77
hopcroft_partition::parray_i
uint * parray_i
Inverse of the previous array: each element in the set is mapped to each index in parray.
Definition nfa_minimization.h:81
hopcroft_partition::rindex
uint * rindex
Array indexed by the classes: each class is mapped to the index following this class in parray.
Definition nfa_minimization.h:82
hopcroft_partition::size_par
uint size_par
The size of the partition.
Definition nfa_minimization.h:78
hopcroft_partition::classes
uint * classes
Array of classes: maps each element to its class.
Definition nfa_minimization.h:79
hopcroft_partition::parray
uint * parray
Array containing all elements of the set grouped by classes (elements belonging to the same class are...
Definition nfa_minimization.h:80
hopcroft_partition::lindex
uint * lindex
Array indexed by the classes: each class is mapped to the index at which this class starts in parray.
Definition nfa_minimization.h:83
nfa
Type used to represent a NFA.
Definition nfa.h:43