Implementation of NFAs. More...

#include "graphs.h"
#include "graphs_transclos.h"
#include "type_abr.h"
#include "type_basic.h"
#include "type_binheap.h"
#include "type_boolarray.h"
#include "type_dequeue.h"
#include "words.h"
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

Classes
struct	nfa
	Type used to represent a NFA. More...

struct	dfa
	Type used to represent a complete DFA. More...

Functions
void	nfa_print_state (const nfa , uint, FILE )
	Displays the name of a state in a NFA on a given stream.

void	dfa_print_state (const dfa , uint, FILE )
	Displays the name of a state in a DFA on a given stream.

void	nfa_reset_state_names (nfa *)
	Release the state names in a NFA (if there are states names).

void	dfa_reset_state_names (dfa *A)
	Release the state names in a DFA (if there are states names).

char **	copy_all_names (char **names, uint size)
	Returns a copy of the array of state names.

void	nfa_delete (nfa *)
	Release of a NFA.

void	dfa_delete (dfa *A)
	Deletes a DFA.

nfa *	nfa_copy (nfa *)
	Copy of a NFA.

dfa *	dfa_copy (dfa *A)
	Copies a DFA.

nfa *	nfa_copy_exalpha (nfa , letter , uint)
	Copies an NFA with an extended alphabet.

dfa *	dfa_copy_exalpha (dfa A, letter alpha, uint size)
	Copies a DFA with an extended alphabet.

void	nfa_overwrite (nfa , nfa )
	Overwrites a NFA by copying another NFA and releasing this other NFA.

nfa *	create_emptylang (void)
	Computes a NFA recognizing the empty language.

nfa *	create_sing_epsilon (void)
	Computes a NFA recognizing the singleton language {ε}.

nfa *	create_sing_letter (letter)
	Computes a NFA recognizing a singleton language {a} containing a single letter word.

nfa *	create_sing_word (word *)
	Computes a NFA recognizing a singleton language {w} for some input word w.

nfa *	nfa_union (void I1, bool is_dfa_I1, void I2, bool is_dfa_I2)
	Union of two automata (NFAs or DFAs) into a single NFA.

nfa *	nfa_concat (void I1, bool is_dfa_I1, void I2, bool is_dfa_I2)
	Concatenation of two NFAs.

nfa *	nfa_star (nfa *)
	Kleene star of a NFA.

nfa *	dfa_star (dfa *)
	Kleene star of a DFA.

nfa *	nfa_plus (nfa *)
	Kleene plus of a NFA.

nfa *	nfa_mirror (nfa *)
	Mirror of a NFA.

nfa *	dfa_mirror (dfa *)
	Mirror of a DFA.

nfa *	nfa_elimeps (nfa *)
	Elimination of the epsilon transitions in a NFA.

void	nfa_elimeps_mod (nfa *)
	Elimination of the epsilon transitions in a NFA. Overwrites the input NFA.

nfa *	nfa_trim (nfa *)
	Elimination of all states that are not simultaneously reachable from an initial state and co-reachable from a final state.

dfa *	dfa_trim (dfa *A)
	Removes all non-accessible states from a DFA.

void	nfa_trim_mod (nfa *)
	Elimination of all states that are not simultaneously reachable from an initial state and co-reachable from a final state. Overwrites the input NFA.

dfa *	dfa_direct_product (dfa A, dfa B)

nfa *	nfa_random (uint, uint, uint)
	Generates a random NFA.

dfa *	dfa_random (uint, uint, uint)
	Generates a random DFA.

int	nfa_nb_trans (nfa *)
	Computes the number of transitions in a NFA.

bool	nfa_is_det (nfa *)
	Tests if a NFA is deterministic.

bool	nfa_is_comp (nfa *)
	Tests if a NFA is complete.

bool	nfa_is_empty (nfa *)
	Tests if a NFA recognizes the empty language.

bool	nfa_accepts (nfa , word )
	Tests if a word is accepted by a NFA.

dequeue *	nfa_compute_runs (nfa , word )
	Computes the set of states reached by a word in a NFA.

bool	dfa_exists_path (dfa , uint, uint, bool )
	Checks if there exists a path between two states in a DFA.

uint	dfa_compute_run (dfa A, word w)
	Computes the run of a DFA on a word.

nfa *	nfa_merge_states (nfa , parti )
	Merges the states of a NFA according to the partition given as input.

dfa *	detnfa_to_dfa (nfa *A)
	Converts a NFA which is deterministic into the complete DFA representation.

nfa *	dfa_to_nfa (dfa *A)
	Converts a DFA into a NFA.

nfa *	dfa_to_nfa_exalpha (dfa A, letter alpha, uint size)
	Converts a DFA into a NFA with an extended alphabet.

Detailed Description

Implementation of NFAs.

Function Documentation

◆ copy_all_names()

char ** copy_all_names	(	char **	names,
		uint	size )

Returns a copy of the array of state names.

Returns: A copy of the array of state names.

Parameters

names	The array of state names.
size	Size of the array of state names.

◆ create_emptylang()

nfa * create_emptylang ( void )

Computes a NFA recognizing the empty language.

Remarks: The computed NFA is defined over an empty alphabet.

Returns: The NFA.

◆ create_sing_epsilon()

nfa * create_sing_epsilon ( void )

Computes a NFA recognizing the singleton language {ε}.

Remarks: The computed NFA is defined over an empty alphabet.

Returns: The NFA.

◆ create_sing_letter()

nfa * create_sing_letter ( letter the_letter )

Computes a NFA recognizing a singleton language {a} containing a single letter word.

Remarks: The computed NFA is defined over the singleton alphabet {a}.

Returns: The NFA.

Parameters

the_letter The letter.

◆ create_sing_word()

nfa * create_sing_word ( word * the_word )

Computes a NFA recognizing a singleton language {w} for some input word w.

Remarks: The computed NFA is defined over the alphabet containing only the letters occurring in w.

Returns: The NFA.

Parameters

the_word The word.

◆ detnfa_to_dfa()

dfa * detnfa_to_dfa ( nfa * A )

Converts a NFA which is deterministic into the complete DFA representation.

Remarks: The function fails if the NFA is not deterministic.; If the NFA is not complete, an additional sink state is added.

Returns: The complete DFA.

Parameters

A The NFA.

◆ dfa_compute_run()

uint dfa_compute_run	(	dfa *	A,
		word *	w )

Computes the run of a DFA on a word.

Returns: The final state reached by the DFA after reading the word. If the word contains an invalid letter, UINT_MAX is returned.

Parameters

A	The DFA.
w	The word.

◆ dfa_copy()

dfa * dfa_copy ( dfa * A )

Copies a DFA.

Returns: A copy of the DFA.

Parameters

A The DFA.

◆ dfa_copy_exalpha()

dfa * dfa_copy_exalpha	(	dfa *	A,
		letter *	alpha,
		uint	size )

Copies a DFA with an extended alphabet.

Remarks: If there indeed new letters in the alphabet, the new DFA is ectended with a new sink state.

Returns: A copy of the DFA with an extended alphabet.

Parameters

A	The DFA.
alpha	Array containing the new letters (sorted in increasing order).
size	Size of the array.

◆ dfa_delete()

void dfa_delete ( dfa * A )

Deletes a DFA.

Parameters

A The DFA.

◆ dfa_direct_product()

dfa * dfa_direct_product	(	dfa *	A,
		dfa *	B )

Parameters

A	The first DFA.
B	The second DFA.

◆ dfa_exists_path()

bool dfa_exists_path	(	dfa *	A,
		uint	in,
		uint	out,
		bool *	alph )

Checks if there exists a path between two states in a DFA.

Attention: The function does not check whether the input is indeed a DFA.

Returns: A Boolean indicating whether there exists a path.

Parameters

A	The DFA.
in	The source state.
out	The target state.
alph	The restriction of the alphabet (NULL if no restriction).

◆ dfa_mirror()

nfa * dfa_mirror ( dfa * A )

Mirror of a DFA.

Returns: A NFA recognizing the mirror of the input language.

Parameters

A The NFA.

◆ dfa_print_state()

void dfa_print_state	(	const dfa *	A,
		uint	q,
		FILE *	out )

Displays the name of a state in a DFA on a given stream.

Remarks: If no names are defined for the states, each state is named by its index.

Parameters

A	The DFA.
q	Index of the state.
out	The stream.

◆ dfa_random()

dfa * dfa_random	(	uint	size_alpha,
		uint	min_size,
		uint	max_size )

Generates a random DFA.

Returns: The random DFA.

Parameters

size_alpha	Size of the alphabet.
min_size	Minimum number of states.
max_size	Maximum number of states.

◆ dfa_reset_state_names()

void dfa_reset_state_names ( dfa * A )

Release the state names in a DFA (if there are states names).

Parameters

A The DFA.

◆ dfa_star()

nfa * dfa_star ( dfa * A )

Kleene star of a DFA.

Returns: A NFA recognizing the Kleene star of the input language.

Parameters

A The DFA.

◆ dfa_to_nfa()

nfa * dfa_to_nfa ( dfa * A )

Converts a DFA into a NFA.

Returns: The NFA.

Parameters

A The DFA.

◆ dfa_to_nfa_exalpha()

nfa * dfa_to_nfa_exalpha	(	dfa *	A,
		letter *	alpha,
		uint	size )

Converts a DFA into a NFA with an extended alphabet.

Returns: The NFA.

◆ dfa_trim()

dfa * dfa_trim ( dfa * A )

Removes all non-accessible states from a DFA.

Returns: The trimmed DFA.

Parameters

A The DFA.

◆ nfa_accepts()

bool nfa_accepts	(	nfa *	A,
		word *	w )

Tests if a word is accepted by a NFA.

Returns: A Boolean indicating whether the word is accepted.

Parameters

A	The NFA.
w	The word.

◆ nfa_compute_runs()

dequeue * nfa_compute_runs	(	nfa *	A,
		word *	w )

Computes the set of states reached by a word in a NFA.

Returns: The list of states reached by the word.

Parameters

A	The NFA.
w	The word.

◆ nfa_concat()

nfa * nfa_concat	(	void *	I1,
		bool	is_dfa_I1,
		void *	I2,
		bool	is_dfa_I2 )

Concatenation of two NFAs.

Remarks: The two NFAs may have dsitinct alphabets. In this case, the alphabet of the computed NFA is the union of the two alphabets.

Returns: A NFA recognizing the concatenation 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.

◆ nfa_copy()

nfa * nfa_copy ( nfa * A )

Copy of a NFA.

Returns: The copy

Parameters

A The NFA.

◆ nfa_copy_exalpha()

nfa * nfa_copy_exalpha	(	nfa *	A,
		letter *	alpha,
		uint	size )

Copies an NFA with an extended alphabet.

Remarks: The input array contains the letters that should be added to the alphabet. It may contain letters which are already in the alphabet. The new alphabet is the union between the old one and the set of letters contains in this array.

Attention: The array containing the new letter must be sorted in increasing order.

Returns: A copy of the original NFA with its alphabet extended.

Parameters

A	The NFA.
alpha	Array containing the new letters (sorted in increasing order).
size	Size of the array.

◆ nfa_delete()

void nfa_delete ( nfa * A )

Release of a NFA.

Parameters

A The NFA.

◆ nfa_elimeps()

nfa * nfa_elimeps ( nfa * A )

Elimination of the epsilon transitions in a NFA.

Returns: A copy of the input NFA with its epsilon transitions eliminated.

Parameters

A The NFA.

◆ nfa_elimeps_mod()

void nfa_elimeps_mod ( nfa * A )

Elimination of the epsilon transitions in a NFA. Overwrites the input NFA.

Parameters

A The NFA.

◆ nfa_is_comp()

bool nfa_is_comp ( nfa * A )

Tests if a NFA is complete.

Returns: A Boolean indicating whether the NFA is complete.

Parameters

A The NFA.

◆ nfa_is_det()

bool nfa_is_det ( nfa * A )

Tests if a NFA is deterministic.

Returns: A Boolean indicating whether the NFA is deterministic.

Parameters

A The NFA.

◆ nfa_is_empty()

bool nfa_is_empty ( nfa * A )

Tests if a NFA recognizes the empty language.

Returns: A Boolean indicating whether the NFA recognizes the empty language.

Parameters

A The NFA.

◆ nfa_merge_states()

nfa * nfa_merge_states	(	nfa *	A,
		parti *	P )

Merges the states of a NFA according to the partition given as input.

The new states are the classes of the partition. Given two classes c,c' and a letter a, a transition (c,a,c') is added if and only if there are two states q in c and q' in c' and a transition (q,a,q') in the original automaton. Similarly, a class c is initial (resp. final) if and only if it contains an intial (resp.final) state.

Returns: The merged NFA.

Parameters

A	The NFA.
P	Partition of the states.

◆ nfa_mirror()

nfa * nfa_mirror ( nfa * A )

Mirror of a NFA.

Returns: A NFA recognizing the mirror of the input language.

Parameters

A The NFA.

◆ nfa_nb_trans()

int nfa_nb_trans ( nfa * A )

Computes the number of transitions in a NFA.

Returns: The number of transitions.

Parameters

A The NFA.

◆ nfa_overwrite()

void nfa_overwrite	(	nfa *	A,
		nfa *	B )

Overwrites a NFA by copying another NFA and releasing this other NFA.

Parameters

A	The NFA that is being overwritten (its original fields are released).
B	The NFA being copied (it is completely released).

◆ nfa_plus()

nfa * nfa_plus ( nfa * A )

Kleene plus of a NFA.

Returns: A NFA recognizing the Kleene plus of the input language.

Parameters

A The NFA.

◆ nfa_print_state()

void nfa_print_state	(	const nfa *	A,
		uint	q,
		FILE *	out )

Displays the name of a state in a NFA on a given stream.

Remarks: If no names are defined for the states, each state is named by its index.

Parameters

A	The NFA.
q	Index of the state.
out	The stream.

◆ nfa_random()

nfa * nfa_random	(	uint	size_alpha,
		uint	min_size,
		uint	max_size )

Generates a random NFA.

Returns: The random NFA.

< At least one initial state.

Parameters

size_alpha	Size of the alphabet.
min_size	Minimum number of states.
max_size	Maximum number of states.

◆ nfa_star()

nfa * nfa_star ( nfa * A )

Kleene star of a NFA.

Returns: A NFA recognizing the Kleene star of the input language.

Parameters

A The NFA.

◆ nfa_trim()

nfa * nfa_trim ( nfa * A )

Elimination of all states that are not simultaneously reachable from an initial state and co-reachable from a final state.

Returns: A copy of the input NFA with its useless states eliminated.

Parameters

A The NFA.

◆ nfa_trim_mod()

void nfa_trim_mod ( nfa * A )

Elimination of all states that are not simultaneously reachable from an initial state and co-reachable from a final state. Overwrites the input NFA.

Parameters

A The NFA.

◆ nfa_union()

nfa * nfa_union	(	void *	I1,
		bool	is_dfa_I1,
		void *	I2,
		bool	is_dfa_I2 )

Union of two automata (NFAs or DFAs) into a single NFA.

Remarks: The two automata may have dsitinct alphabets. In this case, the alphabet of the computed NFA is the union of the two alphabets.

Returns: A NFA recognizing the union 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.

Classes

Functions

Detailed Description

Function Documentation

◆ copy_all_names()

◆ create_emptylang()

◆ create_sing_epsilon()

◆ create_sing_letter()

◆ create_sing_word()

◆ detnfa_to_dfa()

◆ dfa_compute_run()

◆ dfa_copy()

◆ dfa_copy_exalpha()

◆ dfa_delete()

◆ dfa_direct_product()

◆ dfa_exists_path()

◆ dfa_mirror()

◆ dfa_print_state()

◆ dfa_random()

◆ dfa_reset_state_names()

◆ dfa_star()

◆ dfa_to_nfa()

◆ dfa_to_nfa_exalpha()

◆ dfa_trim()

◆ nfa_accepts()

◆ nfa_compute_runs()

◆ nfa_concat()

◆ nfa_copy()

◆ nfa_copy_exalpha()

◆ nfa_delete()

◆ nfa_elimeps()

◆ nfa_elimeps_mod()

◆ nfa_is_comp()

◆ nfa_is_det()

◆ nfa_is_empty()

◆ nfa_merge_states()

◆ nfa_mirror()

◆ nfa_nb_trans()

◆ nfa_overwrite()

◆ nfa_plus()

◆ nfa_print_state()

◆ nfa_random()

◆ nfa_star()

◆ nfa_trim()

◆ nfa_trim_mod()

◆ nfa_union()