nfa_intersec.h File Reference

Intersection of NFAs. More...

#include "nfa.h"
#include "type_dequeue_gen.h"

Go to the source code of this file.

Classes
struct	prod_pair
	Type used for representing a pair of states. More...

Functions
nfa *	nfa_intersect (nfa *, nfa *, bool)
	Intersection of two NFAs with the product automaton construction.
dfa *	dfa_intersect (dfa *, dfa *, bool)
	Intersection of two DFAs with the product automaton construction.
void *	nfa_intersect_mixed (void *I1, bool is_dfa_I1, void *I2, bool is_dfa_I2, bool names)
	Intersection of two NFAs or DFAs.
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).
prod_pair *	dgraph_intersec (dgraph *, dgraph *, uint, uint, uint *)
bool	dgraph_exists_path (dgraph *, uint, uint, bool strict, uint **word)
bool	dgraph_exists_path_alpha (dgraph *, uint s, uint e, bool strict, bool *alpha, uint **word)
uint	dgraph_exists_path_letter_alpha (dgraph *g, uint s, uint b, bool *alpha, uint **word)
bool	dgraph_exists_intersec_path (dgraph *, dgraph *, uint, uint, uint, uint, bool strict, uint **word)
bool	dgraph_exists_intersec_path_alpha (dgraph *, dgraph *, uint, uint, uint, uint, bool strict, bool *alpha, uint **word)

Detailed Description

Intersection of NFAs.

Function Documentation

dfa_intersect()

dfa * dfa_intersect	(	dfa *	A1,
		dfa *	A2,
		bool	names )

Intersection of two DFAs with the product automaton construction.

Remarks

The input Boolean is used to indicate whether the names of the states have to be saved (this only impacts display). The name of a state is the pair of states to which it corresponds.

Returns

The product automaton of the two inputs.

Parameters

A1	The first DFA.
A2	The second DFA.
names	A Boolean indicating whether the state names have to be saved.

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).

Remarks

The input DFA must be deterministic and complete.

Returns

A DFA that is the power product of the input DFA with itself n times.

Parameters

A	The DFA to be iterated.
n	The number of copies of the DFA to be used in the product.
initial_states	List of initial states for each copy of the DFA (the number of initial states must be equal to n).
final_states	List of final states for each copy of the DFA (the number of final states must be equal to n). Optionnal parameter, can be NULL.

dgraph_exists_intersec_path()

bool dgraph_exists_intersec_path	(	dgraph *	g1,
		dgraph *	g2,
		uint	s1,
		uint	s2,
		uint	e1,
		uint	e2,
		bool	strict,
		uint **	word )

Parameters

g1	The first graph
g2	The second graph
s1	Starting state in the first graph.
s2	Starting state in the second graph.
e1	Ending state in the first graph.
e2	Ending state in the second graph.
strict	A Boolean indicating whether the path must be strict (no self-loops).
word	The word that is the intersection path (NULL if not needed).

dgraph_exists_intersec_path_alpha()

bool dgraph_exists_intersec_path_alpha	(	dgraph *	g1,
		dgraph *	g2,
		uint	s1,
		uint	s2,
		uint	e1,
		uint	e2,
		bool	strict,
		bool *	alpha,
		uint **	word )

Parameters

g1	The first graph
g2	The second graph
s1	Starting state in the first graph.
s2	Starting state in the second graph.
e1	Ending state in the first graph.
e2	Ending state in the second graph.
strict	A Boolean indicating whether the path must be strict (no self-loops).
alpha	The alphabet to use for the path (NULL if not needed).
word	The word that is the intersection path (NULL if not needed).

dgraph_exists_path()

bool dgraph_exists_path	(	dgraph *	g,
		uint	s,
		uint	e,
		bool	strict,
		uint **	word )

Parameters

g	The graph
s	Starting state in the graph.
e	Ending state in the graph.
strict	A Boolean indicating whether the path must be strict (no self-loops).
word	The word that is the intersection path (NULL if not needed).

dgraph_exists_path_alpha()

bool dgraph_exists_path_alpha	(	dgraph *	g,
		uint	s,
		uint	e,
		bool	strict,
		bool *	alpha,
		uint **	word )

Parameters

g	The graph
s	Starting state in the graph.
e	Ending state in the graph.
strict	A Boolean indicating whether the path must be strict (no self-loops).
alpha	The alphabet to use for the path (NULL if not needed).
word	The word that is the intersection path (NULL if not needed).

dgraph_exists_path_letter_alpha()

uint dgraph_exists_path_letter_alpha	(	dgraph *	g,
		uint	s,
		uint	b,
		bool *	alpha,
		uint **	word )

Parameters

g	The graph
s	Starting state in the graph.
b	Letter searched.
alpha	The alphabet to use for the path (NULL if not needed).
word	The word that is the intersection path (NULL if not needed).

dgraph_intersec()

prod_pair * dgraph_intersec	(	dgraph *	g1,
		dgraph *	g2,
		uint	s1,
		uint	s2,
		uint *	psize )

Parameters

g1	The first graph
g2	The second graph
s1	Starting state in the first graph.
s2	Starting state in the second graph.
psize	Pointer used to return the size of the computed array.

nfa_intersect()

nfa * nfa_intersect	(	nfa *	A1,
		nfa *	A2,
		bool	names )

Intersection of two NFAs with the product automaton construction.

Remarks

The input Boolean is used to indicate whether the names of the states have to be saved (this only impacts display). The name of a state is the pair of states to which it corresponds.

Returns

The product automaton of the two inputs.

Parameters

A1	The first NFA.
A2	The second NFA.
names	A Boolean indicating whether the state names have to be saved.

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.

Remarks

The two inputs may have distinct alphabets. In this case, the alphabet of the computed NFA is the union of the two alphabets.

Attention

The two inputs must be either both NFAs or both DFAs. If one of the inputs is a DFA and the other is a NFA, the function will return a NFA.

Returns

A NFA or DFA recognizing the intersection of the two input languages.

Parameters

I1	First NFA or DFA.
is_dfa_I1	True if the first input is a DFA, false if it is a NFA.
I2	Second NFA or DFA.
is_dfa_I2	True if the second input is a DFA, false if it is a NFA.
names	A Boolean indicating whether the state names have to be saved.