␈rief A class for the description of automata More...

#include <linguisticProcessing/core/Automaton/automaton.h>

Classes
class	CompareAutomatonMatch

class	DFSStack

Public Types

typedef std::pair< RecognizerMatch, ConstraintCheckList >	AutomatonMatch
	types defined to store the result (or results of the application of the automaton on a graph

typedef std::set< AutomatonMatch, CompareAutomatonMatch >	AutomatonMatchSet

Public Member Functions
	Automaton (const std::string &automId="")
	void constructor initializes an empty automaton (no state, no transition)

	Automaton (const Automaton &a)
	copy constructor

	Automaton (const Tstate nbStates)
	constructor: build an automaton with a predefined number of states, no indications of final states, no transitions

	~Automaton ()
	destructor

Automaton &	operator= (const Automaton &a)
	assignment operator

Tstate	numberOfStates () const
	get the number of states of the automaton

uint64_t	numberOfTransitions () const
	get the number of transitions in the automaton

uint64_t	numberOfTransitions (const Tstate state) const
	find the number of transitions leaving from the state indicated in argument

Transition const &	nthTransition (const Tstate state, const uint64_t n) const
	find the nth transition leaving from a particular state

bool	isFinalState (const Tstate state) const
	test if a given state is a final state of the automaton

std::vector< Tstate >	finalStates () const
	get the list of the final states of the automaton

std::vector< Transition > const &	getTransitionsState (const Tstate state) const
	get the list of transitions leaving from a given state

bool	hasTransitionsState (const Tstate state) const
	test if a state of the automaton has out transitions

bool	isDeterministic () const
	test if the automaton is deterministic or not

void	reinit ()
	reinitializes the automaton (no states, no transitions)

void	setActionHash (const std::vector< std::pair< LimaString, Constraint > > &actionsWithOneArgument)
	set a property hashcode to each transition which represent the constraint(s?) of type action attached to it

bool	getBestMatch (const LinguisticAnalysisStructure::AnalysisGraph &graph, const LinguisticGraphVertex &begin, const LinguisticGraphVertex &limit, AnalysisContent &analysis, RecognizerMatch &longestMatch, ConstraintCheckList &checkList, const SearchGraphSense sense, const AutomatonControlParams &controlParams) const
	test if a text corresponds to the automaton : the text is represented as a LinguisticAnalysisStructure::AnalysisGraph

bool	getAllMatches (const LinguisticAnalysisStructure::AnalysisGraph &graph, const LinguisticGraphVertex &begin, const LinguisticGraphVertex &limit, AnalysisContent &analysis, AutomatonMatchSet &allMatches, ConstraintCheckList &checkList, ForwardSearch &forward, BackwardSearch &backward, const SearchGraphSense sense, const AutomatonControlParams &controlParams) const
	get all matches found between automaton and graph between two points (WARNING: in case of backward search, matches returned are reversed : to to reverse them if natural sense of the graph is needed)

Tstate	addState (bool is_final=false)
	add a state to the automaton

bool	addTransition (Tstate initialState, Tstate finalState, TransitionUnit *transition)
	add a transition between two states

void	removeState (const Tstate state)

void	removeTransition (const Tstate initialState, const TransitionUnit &transition)

void	makeFinal (const Tstate state)
	make a state final

void	unMakeFinal (const Tstate state)
	remove a state from the final states

void	setDeterministic (const bool det)
	set the flag indicating if the automaton is deterministic or not (does not make the automaton deterministic, just set the flag)

Automaton	subsets () const
	make deterministic automaton with the subsets method (does not change the current instance of the autmomaton)

Automaton	reverse () const
	build the automaton that will accept the reverse strings of the language (does not change the current instance of the autmomaton)

Automaton	brzozowskiMinimize () const
	Brzozowski's algorithm for minimization : double reverse and determinization (does not change the current instance of the autmomaton)

void	initializeSearchStructures (MediaId language)

bool	getMatchingTransitions (const LinguisticAnalysisStructure::AnalysisGraph &graph, const LinguisticGraphVertex &vertex, AnalysisContent &analysis, const SearchGraph searchGraph, const Tstate &state, std::vector< std::pair< std::deque< LinguisticGraphVertex >, const Transition > > &matchingTransitions, const LinguisticGraphVertex &limit) const

Protected Types
typedef std::set< Tstate >	SubSet

Protected Member Functions
void	init ()
	profix of identifier of transition

void	copy (const Automaton &a)

void	freeMem ()

bool	testFromState (const Tstate firstState, const LinguisticAnalysisStructure::AnalysisGraph &graph, const LinguisticGraphVertex &begin, const LinguisticGraphVertex &limit, AnalysisContent &analysis, AutomatonMatchSet &results, ConstraintCheckList &checkList, DFSStack &stack, const AutomatonControlParams &controlParams) const

bool	existsEpsilonPathToFinal (const Tstate state) const

std::vector< TransitionUnit * >	collectTransitions () const

bool	isFinalSubset (const SubSet &v) const

void	reachableStates (const SubSet &states, const TransitionUnit &t, SubSet &reachable) const

void	reachableStates (const Tstate &state, const TransitionUnit &t, SubSet &reachable) const

std::string	subsetString (const SubSet &subset) const

Protected Attributes
Tstate	m_numberStates
	number of states in the automaton

std::vector< bool >	m_finalStates
	which states are final states

std::vector< std::vector< Transition > >	m_transitions
	the transitions

std::vector< TransitionSearchStructure< Transition > * >	m_searchStructures

bool	m_deterministic
	a boolean flag indicating if the automaton is deterministic or not

std::string	m_id

Friends
class	AutomatonReader

class	AutomatonWriter

LIMA_AUTOMATON_EXPORT std::ostream &	operator<< (std::ostream &os, const Automaton &a)
	output operator << overloading

LIMA_AUTOMATON_EXPORT QDebug &	operator<< (QDebug &os, const Automaton &a)

LIMA_AUTOMATON_EXPORT std::ostream &	operator<< (std::ostream &os, const DFSStack &x)

LIMA_AUTOMATON_EXPORT QDebug &	operator<< (QDebug &os, const DFSStack &x)

Detailed Description

␈rief A class for the description of automata

this class is used for the definition of the automata implementing local grammars:

The states are simply identified by a number: there is no explicit representation of the states, only a number of states. The number of states is uint64_t.
The transition function is represented by a list of lists, associating to each state the lists of couples (transition, next state)

Definition at line 86 of file automaton.h.

Member Typedef Documentation

◆ AutomatonMatch

typedef std::pair<RecognizerMatch,ConstraintCheckList> Lima::LinguisticProcessing::Automaton::Automaton::AutomatonMatch

types defined to store the result (or results of the application of the automaton on a graph

Definition at line 196 of file automaton.h.

◆ AutomatonMatchSet

typedef std::set<AutomatonMatch,CompareAutomatonMatch> Lima::LinguisticProcessing::Automaton::Automaton::AutomatonMatchSet

Definition at line 203 of file automaton.h.

◆ SubSet

typedef std::set<Tstate> Lima::LinguisticProcessing::Automaton::Automaton::SubSet

protected

Definition at line 374 of file automaton.h.

Constructor & Destructor Documentation

◆ Automaton() [1/3]

Lima::LinguisticProcessing::Automaton::Automaton::Automaton ( const std::string & automId = "" )

void constructor initializes an empty automaton (no state, no transition)

Definition at line 62 of file automaton.cpp.

◆ Automaton() [2/3]

Lima::LinguisticProcessing::Automaton::Automaton::Automaton ( const Automaton & a )

copy constructor

Definition at line 82 of file automaton.cpp.

◆ Automaton() [3/3]

Lima::LinguisticProcessing::Automaton::Automaton::Automaton ( const Tstate nbStates )

constructor: build an automaton with a predefined number of states, no indications of final states, no transitions

Parameters

nbStates : the number of states to reserve

Definition at line 72 of file automaton.cpp.

◆ ~Automaton()

Lima::LinguisticProcessing::Automaton::Automaton::~Automaton ( )

destructor

Definition at line 90 of file automaton.cpp.

Member Function Documentation

◆ addState()

Tstate Lima::LinguisticProcessing::Automaton::Automaton::addState ( bool is_final = false )

add a state to the automaton

Parameters

is_final indicates if the state must be initialized as a final state of the automaton or not

Returns: the identification of the state added

Definition at line 984 of file automaton.cpp.

◆ addTransition()

bool Lima::LinguisticProcessing::Automaton::Automaton::addTransition	(	Tstate	initialState,
		Tstate	finalState,
		TransitionUnit *	transition
	)

add a transition between two states

Parameters

initialState	the initial state
finalState	the final state
transition	the transition unit leading from the initial state to the final state

Returns: true if the transition was added successfully, false otherwise

Definition at line 993 of file automaton.cpp.

◆ brzozowskiMinimize()

Automaton Lima::LinguisticProcessing::Automaton::Automaton::brzozowskiMinimize ( ) const

Brzozowski's algorithm for minimization : double reverse and determinization (does not change the current instance of the autmomaton)

Returns: the minimized automaton

Definition at line 1342 of file automaton.cpp.

◆ collectTransitions()

vector< TransitionUnit * > Lima::LinguisticProcessing::Automaton::Automaton::collectTransitions ( ) const

protected

Definition at line 1232 of file automaton.cpp.

◆ copy()

void Lima::LinguisticProcessing::Automaton::Automaton::copy ( const Automaton & a )

protected

Definition at line 117 of file automaton.cpp.

◆ existsEpsilonPathToFinal()

bool Lima::LinguisticProcessing::Automaton::Automaton::existsEpsilonPathToFinal ( const Tstate state ) const

protected

Definition at line 201 of file automaton.cpp.

◆ finalStates()

vector< Tstate > Lima::LinguisticProcessing::Automaton::Automaton::finalStates ( ) const

get the list of the final states of the automaton

Returns: a vector containing the final states of the automaton

Definition at line 173 of file automaton.cpp.

◆ freeMem()

void Lima::LinguisticProcessing::Automaton::Automaton::freeMem ( )

protected

Definition at line 140 of file automaton.cpp.

◆ getAllMatches()

bool Lima::LinguisticProcessing::Automaton::Automaton::getAllMatches	(	const LinguisticAnalysisStructure::AnalysisGraph &	graph,
		const LinguisticGraphVertex &	begin,
		const LinguisticGraphVertex &	limit,
		AnalysisContent &	analysis,
		AutomatonMatchSet &	allMatches,
		ConstraintCheckList &	checkList,
		ForwardSearch &	forward,
		BackwardSearch &	backward,
		const SearchGraphSense	sense,
		const AutomatonControlParams &	controlParams
	)		const

get all matches found between automaton and graph between two points (WARNING: in case of backward search, matches returned are reversed : to to reverse them if natural sense of the graph is needed)

Parameters

graph	the graph
begin	the first vertex
limit	the last possible vertex
analysis	the current content of the analysis
allMatches	the matches found
checkList	the current state for constraint checking
sense	the sense of search in the graph (FORWARD or BACKWARD)
controlParams	parameters to control the search (for robust treatment of complex graphs)

Returns

Definition at line 708 of file automaton.cpp.

◆ getBestMatch()

bool Lima::LinguisticProcessing::Automaton::Automaton::getBestMatch	(	const LinguisticAnalysisStructure::AnalysisGraph &	graph,
		const LinguisticGraphVertex &	begin,
		const LinguisticGraphVertex &	limit,
		AnalysisContent &	analysis,
		RecognizerMatch &	longestMatch,
		ConstraintCheckList &	checkList,
		const SearchGraphSense	sense,
		const AutomatonControlParams &	controlParams
	)		const

test if a text corresponds to the automaton : the text is represented as a LinguisticAnalysisStructure::AnalysisGraph

Parameters

text	the LinguisticAnalysisStructure::AnalysisGraph corresponding to the beginning of the text to be analyzed
longestMatch	the result
checkList	the current state for constraint checking
sense	the sense of search in the graph (FORWARD or BACKWARD)
controlParams	parameters to control the search (for robust treatment of complex graphs)

Returns: true is a match was found, false otherwise

Definition at line 655 of file automaton.cpp.

◆ getMatchingTransitions()

bool Lima::LinguisticProcessing::Automaton::Automaton::getMatchingTransitions	(	const LinguisticAnalysisStructure::AnalysisGraph &	graph,
		const LinguisticGraphVertex &	vertex,
		AnalysisContent &	analysis,
		const SearchGraph *	searchGraph,
		const Tstate &	state,
		std::vector< std::pair< std::deque< LinguisticGraphVertex >, const Transition * > > &	matchingTransitions,
		const LinguisticGraphVertex &	limit
	)		const

Definition at line 232 of file automaton.cpp.

◆ getTransitionsState()

std::vector< Transition > const & Lima::LinguisticProcessing::Automaton::Automaton::getTransitionsState ( const Tstate state ) const

inline

get the list of transitions leaving from a given state

Parameters

state : the state to consider

Returns: a vector containing the transitions

Definition at line 414 of file automaton.h.

◆ hasTransitionsState()

bool Lima::LinguisticProcessing::Automaton::Automaton::hasTransitionsState ( const Tstate state ) const

test if a state of the automaton has out transitions

Definition at line 183 of file automaton.cpp.

◆ init()

void Lima::LinguisticProcessing::Automaton::Automaton::init ( )

protected

profix of identifier of transition

Definition at line 108 of file automaton.cpp.

◆ initializeSearchStructures()

void Lima::LinguisticProcessing::Automaton::Automaton::initializeSearchStructures ( MediaId language )

Definition at line 214 of file automaton.cpp.

◆ isDeterministic()

bool Lima::LinguisticProcessing::Automaton::Automaton::isDeterministic ( ) const

inline

test if the automaton is deterministic or not

Returns: true if the automaton is deterministic, false otherwise

Definition at line 409 of file automaton.h.

◆ isFinalState()

bool Lima::LinguisticProcessing::Automaton::Automaton::isFinalState ( const Tstate state ) const

inline

test if a given state is a final state of the automaton

Parameters

state : the state to test

Returns: true if the state is a final state, false otherwise

Definition at line 403 of file automaton.h.

◆ isFinalSubset()

bool Lima::LinguisticProcessing::Automaton::Automaton::isFinalSubset ( const SubSet & v ) const

protected

Definition at line 1099 of file automaton.cpp.

◆ makeFinal()

void Lima::LinguisticProcessing::Automaton::Automaton::makeFinal ( const Tstate state )

make a state final

Parameters

state the state to make final

Definition at line 1056 of file automaton.cpp.

◆ nthTransition()

Transition const & Lima::LinguisticProcessing::Automaton::Automaton::nthTransition	(	const Tstate	state,
		const uint64_t	n
	)		const

inline

find the nth transition leaving from a particular state

Parameters

state	: the state
n	: the index of the transition we search for

Returns: the corresponding transition

Definition at line 398 of file automaton.h.

◆ numberOfStates()

Tstate Lima::LinguisticProcessing::Automaton::Automaton::numberOfStates ( ) const

inline

get the number of states of the automaton

Returns: The number of states of the automaton

Definition at line 390 of file automaton.h.

◆ numberOfTransitions() [1/2]

uint64_t Lima::LinguisticProcessing::Automaton::Automaton::numberOfTransitions ( ) const

get the number of transitions in the automaton

Returns: The number of transitions in the automaton

Definition at line 165 of file automaton.cpp.

◆ numberOfTransitions() [2/2]

uint64_t Lima::LinguisticProcessing::Automaton::Automaton::numberOfTransitions ( const Tstate state ) const

inline

find the number of transitions leaving from the state indicated in argument

Parameters

state the state to watch

Returns: the number of transitions from the state

Definition at line 394 of file automaton.h.

◆ operator=()

Automaton & Lima::LinguisticProcessing::Automaton::Automaton::operator= ( const Automaton & a )

assignment operator

Definition at line 97 of file automaton.cpp.

◆ reachableStates() [1/2]

void Lima::LinguisticProcessing::Automaton::Automaton::reachableStates	(	const SubSet &	states,
		const TransitionUnit &	t,
		SubSet &	reachable
	)		const

protected

Definition at line 1258 of file automaton.cpp.

◆ reachableStates() [2/2]

void Lima::LinguisticProcessing::Automaton::Automaton::reachableStates	(	const Tstate &	state,
		const TransitionUnit &	t,
		SubSet &	reachable
	)		const

protected

Definition at line 1270 of file automaton.cpp.

◆ reinit()

void Lima::LinguisticProcessing::Automaton::Automaton::reinit ( )

reinitializes the automaton (no states, no transitions)

Definition at line 156 of file automaton.cpp.

◆ removeState()

void Lima::LinguisticProcessing::Automaton::Automaton::removeState ( const Tstate state )

Definition at line 1040 of file automaton.cpp.

◆ removeTransition()

void Lima::LinguisticProcessing::Automaton::Automaton::removeTransition	(	const Tstate	initialState,
		const TransitionUnit &	transition
	)

Definition at line 1045 of file automaton.cpp.

◆ reverse()

Automaton Lima::LinguisticProcessing::Automaton::Automaton::reverse ( ) const

build the automaton that will accept the reverse strings of the language (does not change the current instance of the autmomaton)

Returns: the reverse automaton obtained

Definition at line 1294 of file automaton.cpp.

◆ setActionHash()

void Lima::LinguisticProcessing::Automaton::Automaton::setActionHash ( const std::vector< std::pair< LimaString, Constraint > > & actionsWithOneArgument )

set a property hashcode to each transition which represent the constraint(s?) of type action attached to it

Definition at line 1190 of file automaton.cpp.

◆ setDeterministic()

void Lima::LinguisticProcessing::Automaton::Automaton::setDeterministic ( const bool det )

set the flag indicating if the automaton is deterministic or not (does not make the automaton deterministic, just set the flag)

Parameters

det	the value to set the flag with (true to say the automaton is deterministic, false to say it is not)

Definition at line 1064 of file automaton.cpp.

◆ subsets()

Automaton Lima::LinguisticProcessing::Automaton::Automaton::subsets ( ) const

make deterministic automaton with the subsets method (does not change the current instance of the autmomaton)

Returns: the deterministic automaton obtained

Definition at line 1111 of file automaton.cpp.

◆ subsetString()

std::string Lima::LinguisticProcessing::Automaton::Automaton::subsetString ( const SubSet & subset ) const

protected

Definition at line 1073 of file automaton.cpp.

◆ testFromState()

bool Lima::LinguisticProcessing::Automaton::Automaton::testFromState	(	const Tstate	firstState,
		const LinguisticAnalysisStructure::AnalysisGraph &	graph,
		const LinguisticGraphVertex &	begin,
		const LinguisticGraphVertex &	limit,
		AnalysisContent &	analysis,
		AutomatonMatchSet &	results,
		ConstraintCheckList &	checkList,
		DFSStack &	stack,
		const AutomatonControlParams &	controlParams
	)		const

protected

Definition at line 759 of file automaton.cpp.

◆ unMakeFinal()

void Lima::LinguisticProcessing::Automaton::Automaton::unMakeFinal ( const Tstate state )

remove a state from the final states

Parameters

state the state to remove

Definition at line 1060 of file automaton.cpp.

Friends And Related Symbol Documentation

◆ AutomatonReader

friend class AutomatonReader

friend

Definition at line 88 of file automaton.h.

◆ AutomatonWriter

friend class AutomatonWriter

friend

Definition at line 89 of file automaton.h.

◆ operator<< [1/4]

LIMA_AUTOMATON_EXPORT QDebug & operator<<	(	QDebug &	os,
		const Automaton &	a
	)

friend

Definition at line 1379 of file automaton.cpp.

◆ operator<< [2/4]

LIMA_AUTOMATON_EXPORT QDebug & operator<<	(	QDebug &	os,
		const DFSStack &	x
	)

friend

Definition at line 473 of file automaton.cpp.

◆ operator<< [3/4]

LIMA_AUTOMATON_EXPORT std::ostream & operator<<	(	std::ostream &	os,
		const Automaton &	a
	)

friend

output operator << overloading

Definition at line 1360 of file automaton.cpp.

◆ operator<< [4/4]

LIMA_AUTOMATON_EXPORT std::ostream & operator<<	(	std::ostream &	os,
		const DFSStack &	x
	)

friend

Definition at line 459 of file automaton.cpp.

Member Data Documentation

◆ m_deterministic

bool Lima::LinguisticProcessing::Automaton::Automaton::m_deterministic

protected

a boolean flag indicating if the automaton is deterministic or not

Definition at line 346 of file automaton.h.

◆ m_finalStates

std::vector<bool> Lima::LinguisticProcessing::Automaton::Automaton::m_finalStates

protected

which states are final states

Definition at line 343 of file automaton.h.

◆ m_id

std::string Lima::LinguisticProcessing::Automaton::Automaton::m_id

protected

Definition at line 348 of file automaton.h.

◆ m_numberStates

Tstate Lima::LinguisticProcessing::Automaton::Automaton::m_numberStates

protected

number of states in the automaton

Definition at line 342 of file automaton.h.

◆ m_searchStructures

std::vector< TransitionSearchStructure<Transition>* > Lima::LinguisticProcessing::Automaton::Automaton::m_searchStructures

protected

Definition at line 345 of file automaton.h.

◆ m_transitions

std::vector< std::vector<Transition> > Lima::LinguisticProcessing::Automaton::Automaton::m_transitions

protected

the transitions

Definition at line 344 of file automaton.h.

The documentation for this class was generated from the following files:

lima_linguisticprocessing/src/linguisticProcessing/core/Automaton/automaton.h
lima_linguisticprocessing/src/linguisticProcessing/core/Automaton/automaton.cpp

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ AutomatonMatch

◆ AutomatonMatchSet

◆ SubSet

Constructor & Destructor Documentation

◆ Automaton() [1/3]

◆ Automaton() [2/3]

◆ Automaton() [3/3]

◆ ~Automaton()

Member Function Documentation

◆ addState()

◆ addTransition()

◆ brzozowskiMinimize()

◆ collectTransitions()

◆ copy()

◆ existsEpsilonPathToFinal()

◆ finalStates()

◆ freeMem()

◆ getAllMatches()

◆ getBestMatch()

◆ getMatchingTransitions()

◆ getTransitionsState()

◆ hasTransitionsState()

◆ init()

◆ initializeSearchStructures()

◆ isDeterministic()

◆ isFinalState()

◆ isFinalSubset()

◆ makeFinal()

◆ nthTransition()

◆ numberOfStates()

◆ numberOfTransitions() [1/2]

◆ numberOfTransitions() [2/2]

◆ operator=()

◆ reachableStates() [1/2]

◆ reachableStates() [2/2]

◆ reinit()

◆ removeState()

◆ removeTransition()

◆ reverse()

◆ setActionHash()

◆ setDeterministic()

◆ subsets()

◆ subsetString()

◆ testFromState()

◆ unMakeFinal()

Friends And Related Symbol Documentation

◆ AutomatonReader

◆ AutomatonWriter

◆ operator<< [1/4]

◆ operator<< [2/4]

◆ operator<< [3/4]

◆ operator<< [4/4]

Member Data Documentation

◆ m_deterministic

◆ m_finalStates

◆ m_id

◆ m_numberStates

◆ m_searchStructures

◆ m_transitions