nfa_determi.h File Reference

Determinization and complementation of NFAs. More...

#include "nfa.h"
#include "printing.h"

Go to the source code of this file.

Classes
struct	dfa_mirror_info
	Represents the required information for determinization of the mirror of a DFA. More...

Functions
dfa *	nfa_determinize (nfa *, bool)
	Determinization of a NFA with the subset construction.
void	dfa_get_mirror_info (dfa *A, dfa_mirror_info *mirror)
	Initializes the dfa_mirror_info structure from a dfa.
dfa *	dfa_determinize_mirror (dfa *, bool)
	Determinization of the mirror of a DFA with the subset construction.
nfa *	nfa_complement (nfa *)
	Complementation of a NFA.
dfa *	dfa_complement (dfa *)
	Complementation of a DFA.

Detailed Description

Determinization and complementation of NFAs.

Function Documentation

dfa_complement()

dfa * dfa_complement

(

dfa *

A

)

Complementation of a DFA.

Returns

A complete DFA recognizing the complement of the input language.

Parameters

A

The DFA.

dfa_determinize_mirror()

dfa * dfa_determinize_mirror	(	dfa *	A,
		bool	names )

Determinization of the mirror of a DFA with the subset construction.

Remarks

The input Boolean is used to indicate whether the names of the states have to be saved (this only impacts display). A stated is named by the corresponding set of states in the subset construction.

Returns

The complete DFA built from the mirror with the subset construction.

Parameters

A	The DFA.
names	A Boolean indicating whether the state names have to be saved.

dfa_get_mirror_info()

void dfa_get_mirror_info	(	dfa *	A,
		dfa_mirror_info *	mirror )

Initializes the dfa_mirror_info structure from a dfa.

Parameters

A	The DFA.
mirror	The structure to be initialized (arrays are allocated by the function).

nfa_complement()

nfa * nfa_complement

(

nfa *

A

)

Complementation of a NFA.

Returns

A complete DFA recognizing the complement of the input language.

Parameters

A

The NFA.

nfa_determinize()

dfa * nfa_determinize	(	nfa *	A,
		bool	names )

Determinization of a NFA with the subset construction.

Remarks

The input Boolean is used to indicate whether the names of the states have to be saved (this only impacts display). A stated is named by the corresponding set of states in the subset construction.

Returns

The complete DFA built with the subset construction.

Parameters

A	The NFA.
names	A Boolean indicating whether the state names have to be saved.