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
NFA.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 <alib/multimap>
27#include <alib/set>
28
29#include <core/components.hpp>
30
33
35
36#include <core/normalize.hpp>
39
40#include "DFA.h"
41
42namespace automaton {
43
44class InputAlphabet;
45class States;
46class FinalStates;
47class InitialState;
48
65template < class SymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType >
66class NFA final : public core::Components < NFA < SymbolTypeT, StateTypeT >, ext::set < SymbolTypeT >, component::Set, InputAlphabet, ext::set < StateTypeT >, component::Set, std::tuple < States, FinalStates >, StateTypeT, component::Value, InitialState > {
67public:
68 typedef SymbolTypeT SymbolType;
69 typedef StateTypeT StateType;
70
71private:
76
77public:
83 explicit NFA ( StateType initialState );
84
93 explicit NFA ( ext::set < StateType > states, ext::set < SymbolType > inputAlphabet, StateType initialState, ext::set < StateType > finalStates );
94
95 /*
96 * \brief Creates a new instance of the automaton based on the Deterministic finite automaton.
97 *
98 * \param other the Deterministic finite automaton
99 */
100 explicit NFA ( const DFA < SymbolType, StateType > & other );
101
107 const StateType & getInitialState ( ) const & {
108 return this->template accessComponent < InitialState > ( ).get ( );
109 }
110
117 return std::move ( this->template accessComponent < InitialState > ( ).get ( ) );
118 }
119
127 bool setInitialState ( StateType state ) {
128 return this->template accessComponent < InitialState > ( ).set ( std::move ( state ) );
129 }
130
136 const ext::set < StateType > & getStates ( ) const & {
137 return this->template accessComponent < States > ( ).get ( );
138 }
139
146 return std::move ( this->template accessComponent < States > ( ).get ( ) );
147 }
148
156 bool addState ( StateType state ) {
157 return this->template accessComponent < States > ( ).add ( std::move ( state ) );
158 }
159
166 this->template accessComponent < States > ( ).set ( std::move ( states ) );
167 }
168
176 void removeState ( const StateType & state ) {
177 this->template accessComponent < States > ( ).remove ( state );
178 }
179
186 return this->template accessComponent < FinalStates > ( ).get ( );
187 }
188
195 return std::move ( this->template accessComponent < FinalStates > ( ).get ( ) );
196 }
197
205 bool addFinalState ( StateType state ) {
206 return this->template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
207 }
208
215 this->template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
216 }
217
225 void removeFinalState ( const StateType & state ) {
226 this->template accessComponent < FinalStates > ( ).remove ( state );
227 }
228
235 return this->template accessComponent < InputAlphabet > ( ).get ( );
236 }
237
244 return std::move ( this->template accessComponent < InputAlphabet > ( ).get ( ) );
245 }
246
254 bool addInputSymbol ( SymbolType symbol ) {
255 return this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbol ) );
256 }
257
264 this->template accessComponent < InputAlphabet > ( ).add ( std::move ( symbols ) );
265 }
266
273 this->template accessComponent < InputAlphabet > ( ).set ( std::move ( symbols ) );
274 }
275
283 void removeInputSymbol ( const SymbolType & symbol ) {
284 this->template accessComponent < InputAlphabet > ( ).remove ( symbol );
285 }
286
300 bool addTransition ( StateType from, SymbolType input, StateType to );
301
313 bool removeTransition ( const StateType & from, const SymbolType & input, const StateType & to );
314
321
327 ext::multimap < ext::pair < StateType, SymbolType >, StateType > && getTransitions ( ) &&;
328
336 auto getTransitionsFromState ( const StateType & from ) const;
337
345 ext::multimap < ext::pair < StateType, SymbolType >, StateType > getTransitionsToState ( const StateType & to ) const;
346
355 bool isDeterministic ( ) const;
356
366 bool isTotal ( ) const;
367
375 auto operator <=> ( const NFA & other ) const {
376 return std::tie ( getStates ( ), getInputAlphabet ( ), getInitialState ( ), getFinalStates ( ), transitions ) <=> std::tie ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ), other.getTransitions ( ) );
377 }
378
386 bool operator == ( const NFA & other ) const {
387 return std::tie ( getStates ( ), getInputAlphabet ( ), getInitialState ( ), getFinalStates ( ), transitions ) == std::tie ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ), other.getTransitions ( ) );
388 }
389
398 friend ext::ostream & operator << ( ext::ostream & out, const NFA & instance ) {
399 return out << "(NFA"
400 << " states = " << instance.getStates ( )
401 << " inputAlphabet = " << instance.getInputAlphabet ( )
402 << " initialState = " << instance.getInitialState ( )
403 << " finalStates = " << instance.getFinalStates ( )
404 << " transitions = " << instance.getTransitions ( )
405 << ")";
406 }
407};
408
414template < class T >
415class isNFA_impl : public std::false_type {};
416
425template < class SymbolType, class StateType >
426class isNFA_impl < NFA < SymbolType, StateType > > : public std::true_type {};
427
433template < class T >
434constexpr bool isNFA = isNFA_impl < T > { };
435
436template<class SymbolType, class StateType >
437NFA < SymbolType, StateType >::NFA ( ext::set < StateType > states, ext::set < SymbolType > inputAlphabet, StateType initialState, ext::set < StateType > finalStates ) : core::Components < NFA, 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 ) ) {
438}
439
440template<class SymbolType, class StateType >
442}
443
444template<class SymbolType, class StateType >
445NFA < SymbolType, StateType >::NFA ( const DFA < SymbolType, StateType > & other ) : NFA ( other.getStates ( ), other.getInputAlphabet ( ), other.getInitialState ( ), other.getFinalStates ( ) ) {
446 transitions.insert ( other.getTransitions ( ).begin ( ), other.getTransitions ( ).end ( ) );
447}
448
449template<class SymbolType, class StateType >
451 if ( ! getStates ( ).contains ( from ) )
452 throw AutomatonException ( "State \"" + ext::to_string ( from ) + "\" doesn't exist." );
453
454 if ( ! getInputAlphabet ( ).contains ( input ) )
455 throw AutomatonException ( "Input symbol \"" + ext::to_string ( input ) + "\" doesn't exist." );
456
457 if ( ! getStates ( ).contains ( to ) )
458 throw AutomatonException ( "State \"" + ext::to_string ( to ) + "\" doesn't exist." );
459
460 auto upper_bound = transitions.upper_bound ( ext::tie ( from, input ) );
461 auto lower_bound = transitions.lower_bound ( ext::tie ( from, input ) );
462 auto iter = std::lower_bound ( lower_bound, upper_bound, to, [ ] ( const auto & transition, const auto & target ) { return transition.second < target; } );
463 if ( iter != upper_bound && to >= iter->second )
464 return false;
465
466 ext::pair < StateType, SymbolType > key = ext::make_pair ( std::move ( from ), std::move ( input ) );
467 transitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( to ) ) );
468 return true;
469}
470
471template<class SymbolType, class StateType >
472bool NFA < SymbolType, StateType >::removeTransition ( const StateType & from, const SymbolType & input, const StateType & to ) {
473 auto upper_bound = transitions.upper_bound ( ext::tie ( from, input ) );
474 auto lower_bound = transitions.lower_bound ( ext::tie ( from, input ) );
475 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] ( const auto & transition ) { return transition.second == to; } );
476 if ( iter == upper_bound )
477 return false;
478
479 transitions.erase ( iter );
480 return true;
481}
482
483template<class SymbolType, class StateType >
485 return transitions;
486}
487
488template<class SymbolType, class StateType >
490 return std::move ( transitions );
491}
492
493template<class SymbolType, class StateType >
495 if ( ! getStates ( ).contains ( from ) )
496 throw AutomatonException ( "State \"" + ext::to_string ( from ) + "\" doesn't exist" );
497
498 return transitions.equal_range ( ext::slice_comp ( from ) );
499}
500
501template<class SymbolType, class StateType >
503 if ( ! getStates ( ).contains ( to ) )
504 throw AutomatonException ( "State \"" + ext::to_string ( to ) + "\" doesn't exist" );
505
507
508 for ( const std::pair < const ext::pair < StateType, SymbolType >, StateType > & transition : transitions )
509 if ( transition.second == to )
510 transitionsToState.insert ( transition );
511
512 return transitionsToState;
513}
514
515template<class SymbolType, class StateType >
517 if ( transitions.empty ( ) )
518 return true;
519
520 for ( auto iter = transitions.begin ( ); std::next ( iter ) != transitions.end ( ); ++ iter )
521 if ( iter->first == std::next ( iter )->first )
522 return false;
523
524 return true;
525}
526
527template<class SymbolType, class StateType >
529 for ( const StateType & state : getStates ( ) ) {
530 for ( const SymbolType & symbol : getInputAlphabet ( ) ) {
531 if ( ! getTransitions ( ).contains ( ext::make_pair ( state, symbol ) ) )
532 return false;
533 }
534 }
535 return true;
536}
537
538} /* namespace automaton */
539
540namespace core {
541
548template<class SymbolType, class StateType >
549class SetConstraint< automaton::NFA < SymbolType, StateType >, SymbolType, automaton::InputAlphabet > {
550public:
559 static bool used ( const automaton::NFA < SymbolType, StateType > & automaton, const SymbolType & symbol ) {
560 for ( const std::pair < const ext::pair < StateType, SymbolType >, StateType > & transition : automaton.getTransitions ( ) )
561 if ( transition.first.second == symbol )
562 return true;
563
564 return false;
565 }
566
576 return true;
577 }
578
586 }
587};
588
595template<class SymbolType, class StateType >
596class SetConstraint< automaton::NFA < SymbolType, StateType >, StateType, automaton::States > {
597public:
606 static bool used ( const automaton::NFA < SymbolType, StateType > & automaton, const StateType & state ) {
607 if ( automaton.getInitialState ( ) == state )
608 return true;
609
610 if ( automaton.getFinalStates ( ).contains ( state ) )
611 return true;
612
613 for ( const std::pair < const ext::pair < StateType, SymbolType >, StateType > & transition : automaton.getTransitions ( ) )
614 if ( ( transition.first.first == state ) || transition.second == state )
615 return true;
616
617 return false;
618 }
619
629 return true;
630 }
631
639 }
640};
641
648template<class SymbolType, class StateType >
649class SetConstraint< automaton::NFA < SymbolType, StateType >, StateType, automaton::FinalStates > {
650public:
659 static bool used ( const automaton::NFA < SymbolType, StateType > &, const StateType & ) {
660 return false;
661 }
662
672 return automaton.template accessComponent < automaton::States > ( ).get ( ).contains ( state );
673 }
674
682 }
683};
684
691template<class SymbolType, class StateType >
692class ElementConstraint< automaton::NFA < SymbolType, StateType >, StateType, automaton::InitialState > {
693public:
703 return automaton.template accessComponent < automaton::States > ( ).get ( ).contains ( state );
704 }
705
713 }
714};
715
721template < class SymbolType, class StateType >
722struct normalize < automaton::NFA < SymbolType, StateType > > {
724 ext::set < DefaultSymbolType > alphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getInputAlphabet ( ) );
725 ext::set < DefaultStateType > states = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getStates ( ) );
726 DefaultStateType initialState = automaton::AutomatonNormalize::normalizeState ( std::move ( value ).getInitialState ( ) );
727 ext::set < DefaultStateType > finalStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getFinalStates ( ) );
728
729 automaton::NFA < > res ( std::move ( states ), std::move ( alphabet ), std::move ( initialState ), std::move ( finalStates ) );
730
731 for ( std::pair < ext::pair < StateType, SymbolType >, StateType > && transition : ext::make_mover ( std::move ( value ).getTransitions ( ) ) ) {
732 DefaultStateType from = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.first.first ) );
733 DefaultSymbolType input = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( transition.first.second ) );
734 DefaultStateType target = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
735
736 res.addTransition ( std::move ( from ), std::move ( input ), std::move ( target ) );
737 }
738
739 return res;
740 }
741};
742
743} /* namespace core */
744
745extern template class automaton::NFA < >;
746
static ext::set< DefaultSymbolType > normalizeAlphabet(ext::set< SymbolType > &&symbols)
Definition: SymbolNormalize.h:50
static DefaultSymbolType normalizeSymbol(SymbolType &&symbol)
Definition: SymbolNormalize.h:68
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
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
StateType && getInitialState() &&
Definition: NFA.h:116
void removeInputSymbol(const SymbolType &symbol)
Definition: NFA.h:283
ext::set< StateType > && getFinalStates() &&
Definition: NFA.h:194
const ext::set< StateType > & getStates() const &
Definition: NFA.h:136
bool isDeterministic() const
Determines whether the automaton is deterministic.
Definition: NFA.h:516
friend ext::ostream & operator<<(ext::ostream &out, const NFA &instance)
Definition: NFA.h:398
bool addState(StateType state)
Definition: NFA.h:156
NFA(StateType initialState)
Creates a new instance of the automaton with a concrete initial state.
Definition: NFA.h:441
ext::set< StateType > && getStates() &&
Definition: NFA.h:145
void addInputSymbols(ext::set< SymbolType > symbols)
Definition: NFA.h:263
const StateType & getInitialState() const &
Definition: NFA.h:107
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: NFA.h:234
const ext::multimap< ext::pair< StateType, SymbolType >, StateType > & getTransitions() const &
Definition: NFA.h:484
const ext::set< StateType > & getFinalStates() const &
Definition: NFA.h:185
ext::multimap< ext::pair< StateType, SymbolType >, StateType > getTransitionsToState(const StateType &to) const
Definition: NFA.h:502
void setFinalStates(ext::set< StateType > states)
Definition: NFA.h:214
bool addInputSymbol(SymbolType symbol)
Definition: NFA.h:254
void removeFinalState(const StateType &state)
Definition: NFA.h:225
void setInputAlphabet(ext::set< SymbolType > symbols)
Definition: NFA.h:272
ext::set< SymbolType > && getInputAlphabet() &&
Definition: NFA.h:243
bool operator==(const NFA &other) const
Definition: NFA.h:386
auto getTransitionsFromState(const StateType &from) const
Definition: NFA.h:494
bool setInitialState(StateType state)
Definition: NFA.h:127
bool removeTransition(const StateType &from, const SymbolType &input, const StateType &to)
Removes a transition from the automaton.
Definition: NFA.h:472
bool addTransition(StateType from, SymbolType input, StateType to)
Add a transition to the automaton.
Definition: NFA.h:450
void removeState(const StateType &state)
Definition: NFA.h:176
bool isTotal() const
Determines whether the automaton is total deterministic.
Definition: NFA.h:528
void setStates(ext::set< StateType > states)
Definition: NFA.h:165
bool addFinalState(StateType state)
Definition: NFA.h:205
StateTypeT StateType
Definition: NFA.h:69
SymbolTypeT SymbolType
Definition: NFA.h:68
Definition: NFA.h:415
Definition: components.hpp:181
static void valid(const automaton::NFA< SymbolType, StateType > &, const StateType &)
Definition: NFA.h:712
static bool available(const automaton::NFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFA.h:702
Definition: components.hpp:25
static bool available(const automaton::NFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFA.h:671
static void valid(const automaton::NFA< SymbolType, StateType > &, const StateType &)
Definition: NFA.h:681
static bool used(const automaton::NFA< SymbolType, StateType > &, const StateType &)
Definition: NFA.h:659
static bool used(const automaton::NFA< SymbolType, StateType > &automaton, const StateType &state)
Definition: NFA.h:606
static void valid(const automaton::NFA< SymbolType, StateType > &, const StateType &)
Definition: NFA.h:638
static bool available(const automaton::NFA< SymbolType, StateType > &, const StateType &)
Definition: NFA.h:628
static bool available(const automaton::NFA< SymbolType, StateType > &, const SymbolType &)
Definition: NFA.h:575
static void valid(const automaton::NFA< SymbolType, StateType > &, const SymbolType &)
Definition: NFA.h:585
static bool used(const automaton::NFA< SymbolType, StateType > &automaton, const SymbolType &symbol)
Definition: NFA.h:559
Definition: setComponents.hpp:26
Class extending the multimap class from the standard library. Original reason is to allow printing of...
Definition: multimap.hpp:48
iterator insert(const T &key, const R &value)
Insert variant with explicit key and value parameters.
Definition: multimap.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
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 isNFA
Definition: NFA.h:434
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
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::NFA< > eval(automaton::NFA< SymbolType, StateType > &&value)
Definition: NFA.h:723
Definition: normalize.hpp:13