Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
NFTA.h
Go to the documentation of this file.
1
6/*
7 * This file is part of Algorithms library toolkit.
8 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
9
10 * Algorithms library toolkit is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14
15 * Algorithms library toolkit is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19
20 * You should have received a copy of the GNU General Public License
21 * along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
22 */
23
24#pragma once
25
26#include <ostream>
27
28#include <alib/multimap>
29#include <alib/set>
30#include <alib/vector>
31
32#include <core/components.hpp>
33
34#include <core/normalize.hpp>
35
38
40
41#include <core/normalize.hpp>
44
45#include "DFTA.h"
46
47namespace automaton {
48
49class InputAlphabet;
50class States;
51class FinalStates;
52
71template < class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType >
72class NFTA final : public core::Components < NFTA < SymbolTypeT, StateTypeT >, ext::set < common::ranked_symbol < SymbolTypeT > >, component::Set, InputAlphabet, ext::set < StateTypeT >, component::Set, std::tuple < States, FinalStates > > {
73public:
74 typedef SymbolTypeT SymbolType;
75 typedef StateTypeT StateType;
76
77private:
82
83public:
87 explicit NFTA ( );
88
97
98 /*
99 * \brief Creates a new instance of the automaton based on the Deterministic finite tree automaton.
100 *
101 * \param other the Deterministic finite tree automaton
102 */
103 explicit NFTA ( const DFTA < SymbolType, StateType > & other );
104
110 const ext::set < StateType > & getStates ( ) const & {
111 return this->template accessComponent < States > ( ).get ( );
112 }
113
120 return std::move ( this->template accessComponent < States > ( ).get ( ) );
121 }
122
130 bool addState ( StateType state ) {
131 return this->template accessComponent < States > ( ).add ( std::move ( state ) );
132 }
133
140 this->template accessComponent < States > ( ).set ( std::move ( states ) );
141 }
142
150 void removeState ( const StateType & state ) {
151 this->template accessComponent < States > ( ).remove ( state );
152 }
153
160 return this->template accessComponent < FinalStates > ( ).get ( );
161 }
162
169 return std::move ( this->template accessComponent < FinalStates > ( ).get ( ) );
170 }
171
179 bool addFinalState ( StateType state ) {
180 return this->template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
181 }
182
189 this->template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
190 }
191
199 void removeFinalState ( const StateType & state ) {
200 this->template accessComponent < FinalStates > ( ).remove ( state );
201 }
202
209 return this->template accessComponent < InputAlphabet > ( ).get ( );
210 }
211
218 return std::move ( this->template accessComponent < InputAlphabet > ( ).get ( ) );
219 }
220
229 return this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbol ) );
230 }
231
238 this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbols ) );
239 }
240
247 this->template accessComponent < InputAlphabet > ( ).set ( std::move ( symbols ) );
248 }
249
258 this->template accessComponent < InputAlphabet > ( ).remove ( symbol );
259 }
260
275
287 bool removeTransition ( const common::ranked_symbol < SymbolType > & symbol, const ext::vector < StateType > & states, const StateType & next );
288
295 return transitions;
296 }
297
304 return std::move ( transitions );
305 }
306
312
313 for ( const auto & transition : getTransitions ( ) )
314 if ( transition.second == q )
315 res.insert ( transition );
316
317 return res;
318 }
319
325
326 for ( const auto & transition : getTransitions ( ) ) {
327 if ( std::find ( transition.first.second.begin ( ), transition.first.second.end ( ), q ) != transition.first.second.end ( ) )
328 res.insert ( transition );
329 }
330
331 return res;
332 }
333
342 bool isDeterministic ( ) const;
343
351 auto operator <=> ( const NFTA & other ) const {
352 return std::tie(getStates(), getInputAlphabet(), getFinalStates(), transitions) <=> std::tie(other.getStates(), other.getInputAlphabet(), other.getFinalStates(), other.transitions);
353 }
354
362 bool operator == ( const NFTA & other ) const {
363 return std::tie(getStates(), getInputAlphabet(), getFinalStates(), transitions) == std::tie(other.getStates(), other.getInputAlphabet(), other.getFinalStates(), other.transitions);
364 }
365
374 friend ext::ostream & operator << ( ext::ostream & out, const NFTA & instance ) {
375 return out << "(NFTA"
376 << " states = " << instance.getStates ( )
377 << " inputAlphabet = " << instance.getInputAlphabet ( )
378 << " finalStates = " << instance.getFinalStates ( )
379 << " transitions = " << instance.getTransitions ( )
380 << ")";
381 }
382};
383
389template < class T >
390class isNFTA_impl : public std::false_type {};
391
400template < class SymbolType, class StateType >
401class isNFTA_impl < NFTA < SymbolType, StateType > > : public std::true_type {};
402
408template < class T >
409constexpr bool isNFTA = isNFTA_impl < T > { };
410
411template < class SymbolType, class StateType >
412NFTA < SymbolType, StateType >::NFTA ( ext::set < StateType > states, ext::set < common::ranked_symbol < SymbolType > > inputAlphabet, ext::set < StateType > finalStates ) : core::Components < NFTA, ext::set < common::ranked_symbol < SymbolType > >, component::Set, InputAlphabet, ext::set < StateType >, component::Set, std::tuple < States, FinalStates > > ( std::move ( inputAlphabet ), std::move ( states ), std::move ( finalStates ) ) {
413}
414
415template < class SymbolType, class StateType >
417}
418
419template < class SymbolType, class StateType >
420NFTA < SymbolType, StateType >::NFTA(const DFTA < SymbolType, StateType > & other) : NFTA ( other.getStates(), other.getInputAlphabet(), other.getFinalStates() ) {
421 transitions.insert ( other.getTransitions ( ).begin ( ), other.getTransitions ( ).end ( ) );
422}
423
424template < class SymbolType, class StateType >
426 if ( prevStates.size ( ) != symbol.getRank ( ) )
427 throw AutomatonException("Number of states doesn't match rank of the symbol");
428
429 if (! getInputAlphabet().count(symbol))
430 throw AutomatonException("Input symbol \"" + ext::to_string ( symbol ) + "\" doesn't exist.");
431
432 if (! getStates().count(next))
433 throw AutomatonException("State \"" + ext::to_string ( next ) + "\" doesn't exist.");
434
435 for (const StateType& it : prevStates) {
436 if (! getStates().count(it))
437 throw AutomatonException("State \"" + ext::to_string ( it ) + "\" doesn't exist.");
438 }
439
440 auto upper_bound = transitions.upper_bound ( ext::tie ( symbol, prevStates ) );
441 auto lower_bound = transitions.lower_bound ( ext::tie ( symbol, prevStates ) );
442 auto iter = std::lower_bound ( lower_bound, upper_bound, next, [ ] ( const auto & transition, const auto & target ) { return transition.second < target; } );
443 if ( iter != upper_bound && next >= iter->second )
444 return false;
445
446 ext::pair < common::ranked_symbol < SymbolType >, ext::vector < StateType > > key = ext::make_pair ( std::move ( symbol ), std::move ( prevStates ) );
447 transitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( next ) ) );
448 return true;
449}
450
451template < class SymbolType, class StateType >
453 auto upper_bound = transitions.upper_bound ( ext::tie ( symbol, states ) );
454 auto lower_bound = transitions.lower_bound ( ext::tie ( symbol, states ) );
455 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] ( const auto & transition ) { return transition.second == next; } );
456 if ( iter == upper_bound )
457 return false;
458
459 transitions.erase ( iter );
460 return true;
461}
462
463template < class SymbolType, class StateType >
465 if ( transitions.empty ( ) )
466 return true;
467
468 for ( auto iter = transitions.begin ( ); std::next ( iter ) != transitions.end ( ); ++ iter )
469 if ( iter->first == std::next ( iter )->first )
470 return false;
471
472 return true;
473}
474
475} /* namespace automaton */
476
477namespace core {
478
485template < class SymbolType, class StateType >
486class SetConstraint< automaton::NFTA < SymbolType, StateType >, common::ranked_symbol < SymbolType >, automaton::InputAlphabet > {
487public:
497 for ( const std::pair<const ext::pair<common::ranked_symbol < SymbolType >, ext::vector<StateType> >, StateType > & t : automaton.getTransitions())
498 if (t.first.first == symbol)
499 return true;
500
501 return false;
502 }
503
513 return true;
514 }
515
523 }
524};
525
532template < class SymbolType, class StateType >
533class SetConstraint< automaton::NFTA < SymbolType, StateType >, StateType, automaton::States > {
534public:
543 static bool used ( const automaton::NFTA < SymbolType, StateType > & automaton, const StateType & state ) {
544 if ( automaton.getFinalStates ( ).count ( state ) )
545 return true;
546
547 for ( const std::pair<const ext::pair<common::ranked_symbol < SymbolType >, ext::vector<StateType> >, StateType >& t : automaton.getTransitions())
548 if(ext::contains(t.first.second.begin(), t.first.second.end(), state ) || t . second == state )
549 return true;
550
551 return false;
552 }
553
563 return true;
564 }
565
573 }
574};
575
582template < class SymbolType, class StateType >
583class SetConstraint< automaton::NFTA < SymbolType, StateType >, StateType, automaton::FinalStates > {
584public:
594 return false;
595 }
596
606 return automaton.template accessComponent < automaton::States > ( ).get ( ).count ( state );
607 }
608
616 }
617};
618
624template < class SymbolType, class StateType >
625struct normalize < automaton::NFTA < SymbolType, StateType > > {
628 ext::set < DefaultStateType > states = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getStates ( ) );
629 ext::set < DefaultStateType > finalStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getFinalStates ( ) );
630
631 automaton::NFTA < > res ( std::move ( states ), std::move ( alphabet ), std::move ( finalStates ) );
632
633 for ( std::pair < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < StateType > >, StateType > && transition : ext::make_mover ( std::move ( value ).getTransitions ( ) ) ) {
635 ext::vector < DefaultStateType > from = automaton::AutomatonNormalize::normalizeStates ( std::move ( transition.first.second ) );
636 DefaultStateType to = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
637
638 res.addTransition ( std::move ( input ), std::move ( from ), std::move ( to ) );
639 }
640
641 return res;
642 }
643};
644
645} /* namespace core */
646
647extern template class automaton::NFTA < >;
648
static common::ranked_symbol< DefaultSymbolType > normalizeRankedSymbol(common::ranked_symbol< SymbolType > &&symbol)
Definition: SymbolNormalize.h:81
static ext::set< common::ranked_symbol< DefaultSymbolType > > normalizeRankedAlphabet(ext::set< common::ranked_symbol< SymbolType > > &&symbols)
Definition: SymbolNormalize.h:59
Definition: AutomatonException.h:15
static DefaultStateType normalizeState(StateType &&state)
Definition: AutomatonNormalize.h:76
static ext::multiset< DefaultStateType > normalizeStates(ext::multiset< StateType > &&states)
Definition: AutomatonNormalize.h:49
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: DFTA.h:74
Nondeterministic finite tree automaton without epsilon transitions. Accepts regular tree languages.
Definition: NFTA.h:72
bool operator==(const NFTA &other) const
Definition: NFTA.h:362
void removeFinalState(const StateType &state)
Definition: NFTA.h:199
bool addTransition(common::ranked_symbol< SymbolType > symbol, ext::vector< StateType > prevStates, StateType next)
Add a transition to the automaton.
Definition: NFTA.h:425
bool removeTransition(const common::ranked_symbol< SymbolType > &symbol, const ext::vector< StateType > &states, const StateType &next)
Removes a transition from the automaton.
Definition: NFTA.h:452
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > getTransitionsFromState(const StateType &q) const
Definition: NFTA.h:323
const ext::set< StateType > & getFinalStates() const &
Definition: NFTA.h:159
ext::set< StateType > && getFinalStates() &&
Definition: NFTA.h:168
bool addState(StateType state)
Definition: NFTA.h:130
void setFinalStates(ext::set< StateType > states)
Definition: NFTA.h:188
friend ext::ostream & operator<<(ext::ostream &out, const NFTA &instance)
Definition: NFTA.h:374
const ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > & getTransitions() const &
Definition: NFTA.h:294
NFTA()
Creates a new instance of the automaton.
Definition: NFTA.h:416
void removeInputSymbol(const common::ranked_symbol< SymbolType > &symbol)
Definition: NFTA.h:257
void removeState(const StateType &state)
Definition: NFTA.h:150
auto operator<=>(const NFTA &other) const
Definition: NFTA.h:351
const ext::set< StateType > & getStates() const &
Definition: NFTA.h:110
SymbolTypeT SymbolType
Definition: NFTA.h:74
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > && getTransitions() &&
Definition: NFTA.h:303
const ext::set< common::ranked_symbol< SymbolType > > & getInputAlphabet() const &
Definition: NFTA.h:208
void setStates(ext::set< StateType > states)
Definition: NFTA.h:139
StateTypeT StateType
Definition: NFTA.h:75
void addInputSymbols(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: NFTA.h:237
ext::set< StateType > && getStates() &&
Definition: NFTA.h:119
bool addFinalState(StateType state)
Definition: NFTA.h:179
ext::multimap< ext::pair< common::ranked_symbol< SymbolType >, ext::vector< StateType > >, StateType > getTransitionsToState(const StateType &q) const
Definition: NFTA.h:310
void setInputAlphabet(ext::set< common::ranked_symbol< SymbolType > > symbols)
Definition: NFTA.h:246
ext::set< common::ranked_symbol< SymbolType > > && getInputAlphabet() &&
Definition: NFTA.h:217
bool addInputSymbol(common::ranked_symbol< SymbolType > symbol)
Definition: NFTA.h:228
bool isDeterministic() const
Determines whether the automaton is deterministic.
Definition: NFTA.h:464
Definition: NFTA.h:390
Definition: ranked_symbol.hpp:20
Definition: components.hpp:181
static bool used(const automaton::NFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFTA.h:543
static void valid(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:572
static bool available(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:562
static void valid(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:615
static bool available(const automaton::NFTA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFTA.h:605
static bool used(const automaton::NFTA< SymbolType, StateType > &, const StateType &)
Definition: NFTA.h:593
static bool used(const automaton::NFTA< SymbolType, StateType > &automaton, const common::ranked_symbol< SymbolType > &symbol)
Definition: NFTA.h:496
static bool available(const automaton::NFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: NFTA.h:512
static void valid(const automaton::NFTA< SymbolType, StateType > &, const common::ranked_symbol< SymbolType > &)
Definition: NFTA.h:522
Definition: setComponents.hpp:26
Class extending the multimap class from the standard library. Original reason is to allow printing of...
Definition: multimap.hpp:48
Definition: ostream.h:14
Class extending the pair class from the standard library. Original reason is to allow printing of the...
Definition: pair.hpp:43
Definition: set.hpp:44
Class extending the vector class from the standard library. Original reason is to allow printing of t...
Definition: vector.hpp:45
Definition: Object.h:16
Definition: BarSymbol.cpp:12
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
p second
Definition: ToRegExpAlgebraic.h:126
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return res
Definition: MinimizeByPartitioning.h:145
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31
constexpr bool isNFTA
Definition: NFTA.h:409
Definition: normalize.hpp:10
constexpr tuple< Elements &... > tie(Elements &... args) noexcept
Helper of extended tuple of references construction. The tuple is constructed to reffer to values in ...
Definition: tuple.hpp:218
reference_mover< T > make_mover(T &param)
Move adaptor construction function specialized to lvalue reference parameter.
Definition: iterator.hpp:468
bool contains(InputIt first, InputIt last, const Element &elem)
Linear version of search in a range of values.
Definition: algorithm.hpp:170
std::string to_string(const T &value)
To string method designated for objects that can be casted to string.
Definition: string.hpp:131
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
static automaton::NFTA< > eval(automaton::NFTA< SymbolType, StateType > &&value)
Definition: NFTA.h:626
Definition: normalize.hpp:13