nfa_minimization.h File Reference

Minimization. More...

#include "nfa_determi.h"
#include "printing.h"

Go to the source code of this file.

Classes
struct	hopcroft_partition
	Type used to represent the state partition used in the Hopcroft algorithm. More...

Functions
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.
dfa *	nfa_brzozowski (nfa *)
	Brzozowski's minimization algorithm (for input NFAs)
dfa *	dfa_brzozowski (dfa *)
	Brzozowski's minimization algorithm (fo rinput DFAs)
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 assumed to be non-trivial.
dfa *	dfa_hopcroft_genauto (dfa *, hopcroft_partition *)
	Computation of the minimal automaton from the partition computed by the Hopcroft's algorithm.
void	dfa_hopcroft_free (hopcroft_partition *)
	Release of a Hopcroft's partition.
dfa *	dfa_hopcroft (dfa *)
	Hopcroft's minimization algorithm.
void	dfa_mini_canonical_ordering (dfa *)
	Computes the canonical ordering of the states of a minimal DFA.

Detailed Description

Minimization.

Two independent algorithms are implemented: Brzozowski and Hopcroft.

Function Documentation

dfa_brzozowski()

dfa * dfa_brzozowski

(

dfa *

A

)

Brzozowski's minimization algorithm (fo rinput DFAs)

Returns

The minimal automaton of the input language.

Parameters

A

The DFA.

dfa_hopcroft()

dfa * dfa_hopcroft

(

dfa *

A

)

Hopcroft's minimization algorithm.

Returns

The minimal automaton of the input DFA.

Parameters

A

The DFA.

dfa_hopcroft_free()

void dfa_hopcroft_free

(

hopcroft_partition *

p

)

Release of a Hopcroft's partition.

Parameters

p	The partition.

dfa_hopcroft_genauto()

dfa * dfa_hopcroft_genauto	(	dfa *	D,
		hopcroft_partition *	p )

Computation of the minimal automaton from the partition computed by the Hopcroft's algorithm.

Returns

The minimal automaton.

Parameters

D	The original complete DFA.
p	The partition.

dfa_hopcroft_initial()

hopcroft_partition * dfa_hopcroft_initial	(	uint	size_auto,
		uint *	finals,
		uint	nb_finals )

Computes the initial partition of the states in Hopcroft's algorithm. The set of final states is assumed to be non-trivial.

Remarks

The computed partition has two classes since the set of final states is non-trivial.

Returns

The initial partition.

Parameters

size_auto	The number of states in the automaton.
finals	The list of final states (assumed to be non-trivial).
nb_finals	The number of final states (assumed to be non-trivial).

dfa_mini_canonical_copy()

dfa * dfa_mini_canonical_copy

(

dfa *

A

)

Makes a copy of a minimal DFA. The ordering between the states is changed to make the copy canonical.

Attention

The input DFA is assumed to be minimal. This is not checked.

Returns

The canonical copy of the input DFA.

Parameters

A	The DFA to copy.

dfa_mini_canonical_ordering()

void dfa_mini_canonical_ordering

(

dfa *

A

)

Computes the canonical ordering of the states of a minimal DFA.

Canonical ordering

Returns

The canonical ordering of the states.

Attention

The input DFA is assumed to be minimal. This is not checked.

Canonical ordering

Parameters

A	The DFA to order (must be minimal).

nfa_brzozowski()

dfa * nfa_brzozowski

(

nfa *

A

)

Brzozowski's minimization algorithm (for input NFAs)

Returns

The minimal automaton of the input language.

Parameters

A

The NFA.