Mescal
Loading...
Searching...
No Matches
nfa_intersec.h
Go to the documentation of this file.
1
6
7#ifndef NFA_INTERSEC_H
8#define NFA_INTERSEC_H
9
10 /* _ _ _____ _ ___ _ _ _ */
11 /* | \ | | ___/ \ _ |_ _|_ __ | |_ ___ _ __ ___ ___ ___| |_(_) ___ _ __ */
12 /* | \| | |_ / _ \ (_) | || '_ \| __/ _ \ '__/ __|/ _ \/ __| __| |/ _ \| '_ \ */
13 /* | |\ | _/ ___ \ _ | || | | | || __/ | \__ \ __/ (__| |_| | (_) | | | | */
14 /* |_| \_|_|/_/ \_(_) |___|_| |_|\__\___|_| |___/\___|\___|\__|_|\___/|_| |_| */
15
16#include "nfa.h"
17#include "type_dequeue_gen.h"
18
19//#define NFA_INTER_DEBUG
20
21
33nfa* nfa_intersect(nfa*,
34 nfa*,
35 bool
36);
37
49dfa* dfa_intersect(dfa*,
50 dfa*,
51 bool
52);
53
68void* nfa_intersect_mixed(void* I1,
69 bool is_dfa_I1,
70 void* I2,
71 bool is_dfa_I2,
72 bool names
73);
74
85dfa* dfa_power_prod(dfa* A,
86 uint n,
87 int* initial_states,
88 int* final_states
89);
90
91
92
97typedef struct {
98 uint q1;
99 uint q2;
100} prod_pair;
101
102
103prod_pair* dgraph_intersec(dgraph*,
104 dgraph*,
105 uint,
106 uint,
107 uint*
108);
109
110bool dgraph_exists_path(dgraph*,
111 uint,
112 uint,
113 bool strict,
114 uint** word
115);
116
117bool dgraph_exists_path_alpha(dgraph*,
118 uint s,
119 uint e,
120 bool strict,
121 bool* alpha,
122 uint** word
123);
124
125uint dgraph_exists_path_letter_alpha(dgraph* g,
126 uint s,
127 uint b,
128 bool* alpha,
129 uint** word
130);
131
132
133
134
135bool dgraph_exists_intersec_path(dgraph*,
136 dgraph*,
137 uint,
138 uint,
139 uint,
140 uint,
141 bool strict,
142 uint** word
143);
144
145bool dgraph_exists_intersec_path_alpha(dgraph*,
146 dgraph*,
147 uint,
148 uint,
149 uint,
150 uint,
151 bool strict,
152 bool* alpha,
153 uint** word
154);
155
156
157
158#endif
nfa.h
Implementation of NFAs.
dfa_power_prod
dfa * dfa_power_prod(dfa *A, uint n, int *initial_states, int *final_states)
Computes the power product of a DFA (for specified initial states).
Definition nfa_intersec.c:664
dgraph_exists_intersec_path
bool dgraph_exists_intersec_path(dgraph *, dgraph *, uint, uint, uint, uint, bool strict, uint **word)
Definition nfa_intersec.c:1158
nfa_intersect
nfa * nfa_intersect(nfa *, nfa *, bool)
Intersection of two NFAs with the product automaton construction.
Definition nfa_intersec.c:140
dgraph_exists_path_alpha
bool dgraph_exists_path_alpha(dgraph *, uint s, uint e, bool strict, bool *alpha, uint **word)
Definition nfa_intersec.c:968
dfa_intersect
dfa * dfa_intersect(dfa *, dfa *, bool)
Intersection of two DFAs with the product automaton construction.
Definition nfa_intersec.c:468
dgraph_intersec
prod_pair * dgraph_intersec(dgraph *, dgraph *, uint, uint, uint *)
Definition nfa_intersec.c:788
dgraph_exists_path
bool dgraph_exists_path(dgraph *, uint, uint, bool strict, uint **word)
Definition nfa_intersec.c:880
nfa_intersect_mixed
void * nfa_intersect_mixed(void *I1, bool is_dfa_I1, void *I2, bool is_dfa_I2, bool names)
Intersection of two NFAs or DFAs.
Definition nfa_intersec.c:631
dgraph_exists_path_letter_alpha
uint dgraph_exists_path_letter_alpha(dgraph *g, uint s, uint b, bool *alpha, uint **word)
Definition nfa_intersec.c:1063
dgraph_exists_intersec_path_alpha
bool dgraph_exists_intersec_path_alpha(dgraph *, dgraph *, uint, uint, uint, uint, bool strict, bool *alpha, uint **word)
Definition nfa_intersec.c:1279
dfa
Type used to represent a complete DFA.
Definition nfa.h:61
dgraph
Type used to represent a complete deterministic directed labeled graph.
Definition graphs.h:73
nfa
Type used to represent a NFA.
Definition nfa.h:43
prod_pair
Type used for representing a pair of states.
Definition nfa_intersec.h:97
prod_pair::q1
uint q1
First state.
Definition nfa_intersec.h:98
prod_pair::q2
uint q2
Second state.
Definition nfa_intersec.h:99
word
The type used to represent a word.
Definition words.h:143
type_dequeue_gen.h
Implementation of generic dequeues which store void pointers.