Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
CompactDFA.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/map>
29#include <alib/set>
30
31#include <ext/algorithm>
32
33#include <core/components.hpp>
35
38
40
42
43#include <core/normalize.hpp>
46
47#include "DFA.h"
48
49namespace automaton {
50
51class InputAlphabet;
52class States;
53class FinalStates;
54class InitialState;
55
72template < class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType >
73class CompactDFA final : public core::Components < CompactDFA < SymbolTypeT, StateTypeT >, ext::set < SymbolTypeT >, component::Set, InputAlphabet, ext::set < StateTypeT >, component::Set, std::tuple < States, FinalStates >, StateTypeT, component::Value, InitialState > {
74public:
75 typedef SymbolTypeT SymbolType;
76 typedef StateTypeT StateType;
77
78private:
83
84public:
90 explicit CompactDFA ( StateType initialState );
91
100 explicit CompactDFA ( ext::set < StateType > states, ext::set < SymbolType > inputAlphabet, StateType initialState, ext::set < StateType > finalStates );
101
102 /*
103 * \brief Creates a new instance of the automaton based on the Deterministic finite automaton.
104 *
105 * \param other the Deterministic finite automaton
106 */
107 explicit CompactDFA ( const DFA < SymbolType, StateType > & other );
108
114 const StateType & getInitialState ( ) const & {
115 return this->template accessComponent < InitialState > ( ).get ( );
116 }
117
124 return std::move ( this->template accessComponent < InitialState > ( ).get ( ) );
125 }
126
134 bool setInitialState ( StateType state ) {
135 return this->template accessComponent < InitialState > ( ).set ( std::move ( state ) );
136 }
137
143 const ext::set < StateType > & getStates ( ) const & {
144 return this->template accessComponent < States > ( ).get ( );
145 }
146
153 return std::move ( this->template accessComponent < States > ( ).get ( ) );
154 }
155
163 bool addState ( StateType state ) {
164 return this->template accessComponent < States > ( ).add ( std::move ( state ) );
165 }
166
173 this->template accessComponent < States > ( ).set ( std::move ( states ) );
174 }
175
183 void removeState ( const StateType & state ) {
184 this->template accessComponent < States > ( ).remove ( state );
185 }
186
193 return this->template accessComponent < FinalStates > ( ).get ( );
194 }
195
202 return std::move ( this->template accessComponent < FinalStates > ( ).get ( ) );
203 }
204
212 bool addFinalState ( StateType state ) {
213 return this->template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
214 }
215
222 this->template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
223 }
224
232 void removeFinalState ( const StateType & state ) {
233 this->template accessComponent < FinalStates > ( ).remove ( state );
234 }
235
242 return this->template accessComponent < InputAlphabet > ( ).get ( );
243 }
244
251 return std::move ( this->template accessComponent < InputAlphabet > ( ).get ( ) );
252 }
253
261 bool addInputSymbol ( SymbolType symbol ) {
262 return this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbol ) );
263 }
264
271 this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbols ) );
272 }
273
280 this->template accessComponent < InputAlphabet > ( ).set ( std::move ( symbols ) );
281 }
282
290 void removeInputSymbol ( const SymbolType & symbol ) {
291 this->template accessComponent < InputAlphabet > ( ).remove ( symbol );
292 }
293
308
320 bool removeTransition ( const StateType & from, const ext::vector < SymbolType > & input, const StateType & to );
321
328
334 ext::map < ext::pair < StateType, ext::vector < SymbolType > >, StateType > && getTransitions ( ) &&;
335
343 ext::iterator_range < typename ext::map < ext::pair < StateType, ext::vector < SymbolType > >, StateType >::const_iterator > getTransitionsFromState ( const StateType & from ) const;
344
352 ext::map < ext::pair < StateType, ext::vector < SymbolType > >, StateType > getTransitionsToState ( const StateType & to ) const;
353
361 auto operator <=> ( const CompactDFA & other ) const {
362 return std::tie ( getStates ( ), getInputAlphabet ( ), getInitialState ( ), getFinalStates ( ), transitions ) <=> std::tie ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ), other.getTransitions ( ) );
363 }
364
372 bool operator == ( const CompactDFA & other ) const {
373 return std::tie ( getStates ( ), getInputAlphabet ( ), getInitialState ( ), getFinalStates ( ), transitions ) == std::tie ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ), other.getTransitions ( ) );
374 }
375
384 friend ext::ostream & operator << ( ext::ostream & out, const CompactDFA & instance ) {
385 return out << "(CompactDFA"
386 << " states = " << instance.getStates ( )
387 << " inputAlphabet = " << instance.getInputAlphabet ( )
388 << " initialState = " << instance.getInitialState ( )
389 << " finalStates = " << instance.getFinalStates ( )
390 << " transitions = " << instance.getTransitions ( )
391 << ")";
392 }
393};
394
400template < class T >
401class isCompactDFA_impl : public std::false_type {};
402
411template < class SymbolType, class StateType >
412class isCompactDFA_impl < CompactDFA < SymbolType, StateType > > : public std::true_type {};
413
419template < class T >
421
422template < class SymbolType, class StateType >
423CompactDFA < SymbolType, StateType >::CompactDFA ( ext::set < StateType > states, ext::set < SymbolType > inputAlphabet, StateType initialState, ext::set < StateType > finalStates ) : core::Components < CompactDFA, ext::set < SymbolType >, component::Set, InputAlphabet, ext::set < StateType >, component::Set, std::tuple < States, FinalStates >, StateType, component::Value, InitialState > ( std::move ( inputAlphabet ), std::move ( states ), std::move ( finalStates ), std::move ( initialState ) ) {
424}
425
426template < class SymbolType, class StateType >
428}
429
430template < class SymbolType, class StateType >
431CompactDFA < SymbolType, StateType >::CompactDFA ( const DFA < SymbolType, StateType > & other ) : CompactDFA ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ) ) {
432 for ( const auto & transition : other.getTransitions ( ) )
433 transitions.insert ( ext::make_pair ( transition.first.first, ext::vector < SymbolType > { transition.first.second } ), transition.second );
434}
435
436template < class SymbolType, class StateType >
438 if ( ! getStates ( ).contains ( from ) )
439 throw AutomatonException ( "State \"" + ext::to_string ( from ) + "\" doesn't exist." );
440
441 ext::set < SymbolType > inputStringAlphabet ( input.begin ( ), input.end ( ) );
442
443 // Transition regexp's alphabet must be subset of automaton's alphabet
444 if ( ! std::includes ( getInputAlphabet ( ).begin ( ), getInputAlphabet ( ).end ( ), inputStringAlphabet.begin ( ), inputStringAlphabet.end ( ) ) )
445 throw AutomatonException ( "Input string is over different alphabet than automaton" );
446
447 if ( ! getStates ( ).contains ( to ) )
448 throw AutomatonException ( "State \"" + ext::to_string ( to ) + "\" doesn't exist." );
449
450 ext::pair < StateType, ext::vector < SymbolType > > key = ext::make_pair ( std::move ( from ), std::move ( input ) );
451 if ( transitions.find ( key ) != transitions.end ( ) )
452 return false;
453
454 auto transitionsFromState = getTransitionsFromState ( key.first );
455 if ( key.second.empty ( ) && ! transitionsFromState.empty ( ) )
456 throw AutomatonException ( "Epsilon transition from state \"" + ext::to_string ( key.first ) + "\" coflicts already existent transitions." );
457
458 for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & transition : getTransitionsFromState ( key.first ) )
459 if ( transition.first.second.empty ( ) || transition.first.second [ 0 ] == key.second [ 0 ] )
460 throw AutomatonException ( "Transition from state \"" + ext::to_string ( key.first ) + "\" reading symbol \"" + ext::to_string ( key.second ) + "\" already exists. Targeto state was \"" + ext::to_string ( to ) + "\"." );
461
462 transitions.insert ( std::move ( key ), std::move ( to ) );
463 return true;
464}
465
466template < class SymbolType, class StateType >
469
470 auto iter = transitions.find ( key );
471
472 if ( iter == transitions.end ( ) )
473 return false;
474
475 if ( iter->second != to )
476 return false;
477
478 transitions.erase ( iter );
479 return true;
480}
481
482template < class SymbolType, class StateType >
484 return transitions;
485}
486
487template < class SymbolType, class StateType >
489 return std::move ( transitions );
490}
491
492template<class SymbolType, class StateType >
494 if ( ! getStates ( ).contains ( from ) )
495 throw AutomatonException ( "State \"" + ext::to_string ( from ) + "\" doesn't exist" );
496
497 auto lower = transitions.lower_bound ( ext::slice_comp ( from ) );
498 auto upper = transitions.upper_bound ( ext::slice_comp ( from ) );
499
500 return ext::make_iterator_range ( lower, upper );
501}
502
503template < class SymbolType, class StateType >
505 if ( ! getStates ( ).contains ( to ) )
506 throw AutomatonException ( "State \"" + ext::to_string ( to ) + "\" doesn't exist" );
507
509
510 for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & transition : transitions )
511 if ( transition.second == to )
512 transitionsToState.insert ( transition );
513
514 return transitionsToState;
515}
516
517} /* namespace automaton */
518
519namespace core {
520
527template < class SymbolType, class StateType >
528class SetConstraint< automaton::CompactDFA < SymbolType, StateType >, SymbolType, automaton::InputAlphabet > {
529public:
539 for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & transition : automaton.getTransitions ( ) ) {
540 ext::set < SymbolType > alphabet ( transition.first.second.begin ( ), transition.first.second.end ( ) );
541 if ( alphabet.contains ( symbol ) )
542 return true;
543 }
544
545 return false;
546 }
547
557 return true;
558 }
559
567 }
568};
569
576template < class SymbolType, class StateType >
577class SetConstraint< automaton::CompactDFA < SymbolType, StateType >, StateType, automaton::States > {
578public:
588 if ( automaton.getInitialState ( ) == state )
589 return true;
590
591 if ( automaton.getFinalStates ( ).contains ( state ) )
592 return true;
593
594 for ( const std::pair < const ext::pair < StateType, ext::vector < SymbolType > >, StateType > & t : automaton.getTransitions ( ) )
595 if ( ( t.first.first == state ) || t.second == state )
596 return true;
597
598 return false;
599 }
600
610 return true;
611 }
612
620 }
621};
622
629template < class SymbolType, class StateType >
630class SetConstraint< automaton::CompactDFA < SymbolType, StateType >, StateType, automaton::FinalStates > {
631public:
641 return false;
642 }
643
653 return automaton.template accessComponent < automaton::States > ( ).get ( ).contains ( state );
654 }
655
663 }
664};
665
672template < class SymbolType, class StateType >
673class ElementConstraint< automaton::CompactDFA < SymbolType, StateType >, StateType, automaton::InitialState > {
674public:
684 return automaton.template accessComponent < automaton::States > ( ).get ( ).contains ( state );
685 }
686
694 }
695};
696
702template < class SymbolType, class StateType >
703struct normalize < automaton::CompactDFA < SymbolType, StateType > > {
705 ext::set < DefaultSymbolType > alphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getInputAlphabet ( ) );
706 ext::set < DefaultStateType > states = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getStates ( ) );
707 DefaultStateType initialState = automaton::AutomatonNormalize::normalizeState ( std::move ( value ).getInitialState ( ) );
708 ext::set < DefaultStateType > finalStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getFinalStates ( ) );
709
710 automaton::CompactDFA < > res ( std::move ( states ), std::move ( alphabet ), std::move ( initialState ), std::move ( finalStates ) );
711
712 for ( std::pair < ext::pair < StateType, ext::vector < SymbolType > >, StateType > && transition : ext::make_mover ( std::move ( value ).getTransitions ( ) ) ) {
713 DefaultStateType from = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.first.first ) );
714 ext::vector < DefaultSymbolType > input = alphabet::SymbolNormalize::normalizeSymbols ( std::move ( transition.first.second ) );
715 DefaultStateType target = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
716
717 res.addTransition ( std::move ( from ), std::move ( input ), target );
718 }
719
720 return res;
721 }
722};
723
724} /* namespace core */
725
726extern template class automaton::CompactDFA < >;
727
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static ext::vector< DefaultSymbolType > normalizeSymbols(ext::vector< SymbolType > &&symbols)
Definition: SymbolNormalize.h:86
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
Compact deterministic finite automaton. Accepts regular languages. The automaton has a list of symbol...
Definition: CompactDFA.h:73
void addInputSymbols(ext::set< SymbolType > symbols)
Definition: CompactDFA.h:270
SymbolTypeT SymbolType
Definition: CompactDFA.h:75
StateType && getInitialState() &&
Definition: CompactDFA.h:123
CompactDFA(StateType initialState)
Creates a new instance of the automaton with a concrete initial state.
Definition: CompactDFA.h:427
const ext::map< ext::pair< StateType, ext::vector< SymbolType > >, StateType > & getTransitions() const &
Definition: CompactDFA.h:483
ext::set< SymbolType > && getInputAlphabet() &&
Definition: CompactDFA.h:250
bool addFinalState(StateType state)
Definition: CompactDFA.h:212
ext::set< StateType > && getStates() &&
Definition: CompactDFA.h:152
ext::map< ext::pair< StateType, ext::vector< SymbolType > >, StateType > getTransitionsToState(const StateType &to) const
Definition: CompactDFA.h:504
bool addState(StateType state)
Definition: CompactDFA.h:163
void setFinalStates(ext::set< StateType > states)
Definition: CompactDFA.h:221
bool operator==(const CompactDFA &other) const
Definition: CompactDFA.h:372
bool setInitialState(StateType state)
Definition: CompactDFA.h:134
const ext::set< StateType > & getFinalStates() const &
Definition: CompactDFA.h:192
bool removeTransition(const StateType &from, const ext::vector< SymbolType > &input, const StateType &to)
Removes a transition from the automaton.
Definition: CompactDFA.h:467
friend ext::ostream & operator<<(ext::ostream &out, const CompactDFA &instance)
Definition: CompactDFA.h:384
const StateType & getInitialState() const &
Definition: CompactDFA.h:114
const ext::set< StateType > & getStates() const &
Definition: CompactDFA.h:143
bool addTransition(StateType from, ext::vector< SymbolType > input, StateType to)
Add a transition to the automaton.
Definition: CompactDFA.h:437
bool addInputSymbol(SymbolType symbol)
Definition: CompactDFA.h:261
void removeFinalState(const StateType &state)
Definition: CompactDFA.h:232
void setInputAlphabet(ext::set< SymbolType > symbols)
Definition: CompactDFA.h:279
void removeInputSymbol(const SymbolType &symbol)
Definition: CompactDFA.h:290
StateTypeT StateType
Definition: CompactDFA.h:76
ext::iterator_range< typename ext::map< ext::pair< StateType, ext::vector< SymbolType > >, StateType >::const_iterator > getTransitionsFromState(const StateType &from) const
Definition: CompactDFA.h:493
void setStates(ext::set< StateType > states)
Definition: CompactDFA.h:172
ext::set< StateType > && getFinalStates() &&
Definition: CompactDFA.h:201
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: CompactDFA.h:241
void removeState(const StateType &state)
Definition: CompactDFA.h:183
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
Definition: CompactDFA.h:401
Definition: components.hpp:181
static void valid(const automaton::CompactDFA< SymbolType, StateType > &, const StateType &)
Definition: CompactDFA.h:693
static bool available(const automaton::CompactDFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: CompactDFA.h:683
Definition: components.hpp:25
static bool available(const automaton::CompactDFA< SymbolType, StateType > &, const SymbolType &)
Definition: CompactDFA.h:556
static bool used(const automaton::CompactDFA< SymbolType, StateType > &automaton, const SymbolType &symbol)
Definition: CompactDFA.h:538
static void valid(const automaton::CompactDFA< SymbolType, StateType > &, const SymbolType &)
Definition: CompactDFA.h:566
static bool used(const automaton::CompactDFA< SymbolType, StateType > &, const StateType &)
Definition: CompactDFA.h:640
static void valid(const automaton::CompactDFA< SymbolType, StateType > &, const StateType &)
Definition: CompactDFA.h:662
static bool available(const automaton::CompactDFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: CompactDFA.h:652
static void valid(const automaton::CompactDFA< SymbolType, StateType > &, const StateType &)
Definition: CompactDFA.h:619
static bool available(const automaton::CompactDFA< SymbolType, StateType > &, const StateType &)
Definition: CompactDFA.h:609
static bool used(const automaton::CompactDFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: CompactDFA.h:587
Definition: setComponents.hpp:26
Implementation of iterator_range, i.e. pair of iterators. The class provides most notably begin and e...
Definition: range.hpp:24
Class extending the map class from the standard library. Original reason is to allow printing of the ...
Definition: map.hpp:48
std::pair< iterator, bool > insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: map.hpp:118
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
auto begin() &
Inherited behavior of begin for non-const instance.
Definition: set.hpp:99
auto end() &
Inherited behavior of end for non-const instance.
Definition: set.hpp:129
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
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
return res
Definition: MinimizeByPartitioning.h:145
Definition: ToGrammar.h:31
constexpr bool isCompactDFA
Definition: CompactDFA.h:420
Definition: normalize.hpp:10
Definition: sigHandler.cpp:20
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
SliceComp< Ts ... > slice_comp(const Ts &... inst)
Definition: functional.hpp:95
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
iterator_range< Iter > make_iterator_range(Iter begin, Iter end)
Helper to create iterator_range from two iterators.
Definition: range.hpp:235
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79
auto begin(Container &&cont) -> decltype(std::forward(cont).begin())
Definition: iterator.hpp:900
void end()
Definition: measurements.cpp:19
auto & get(ext::ptr_array< Type, N > &tpl)
Specialisation of get function for pointer arrays.
Definition: ptr_array.hpp:693
static automaton::CompactDFA< > eval(automaton::CompactDFA< SymbolType, StateType > &&value)
Definition: CompactDFA.h:704
Definition: normalize.hpp:13