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
VisiblyPushdownNPDA.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
27#include <ext/algorithm>
28
29#include <alib/multimap>
30#include <alib/set>
31#include <alib/vector>
32
33#include <core/components.hpp>
34
37
39
40#include <core/normalize.hpp>
43
44namespace automaton {
45
46class CallAlphabet;
47class ReturnAlphabet;
48class LocalAlphabet;
49class PushdownStoreAlphabet;
50class BottomOfTheStackSymbol;
51class States;
52class FinalStates;
53class InitialStates;
54
80template < class InputSymbolTypeT = DefaultSymbolType, class PushdownStoreSymbolTypeT = DefaultSymbolType, class StateTypeT = DefaultStateType >
81class VisiblyPushdownNPDA final : public core::Components < VisiblyPushdownNPDA < InputSymbolTypeT, PushdownStoreSymbolTypeT, StateTypeT >, ext::set < InputSymbolTypeT >, component::Set, std::tuple < CallAlphabet, ReturnAlphabet, LocalAlphabet >, ext::set < PushdownStoreSymbolTypeT >, component::Set, PushdownStoreAlphabet, PushdownStoreSymbolTypeT, component::Value, BottomOfTheStackSymbol, ext::set < StateTypeT >, component::Set, std::tuple < States, InitialStates, FinalStates > > {
82public:
83 typedef InputSymbolTypeT InputSymbolType;
84 typedef PushdownStoreSymbolTypeT PushdownStoreSymbolType;
85 typedef StateTypeT StateType;
86
87private:
92
97
102
103public:
116 explicit VisiblyPushdownNPDA ( ext::set < StateType > states, ext::set < InputSymbolType > callAlphabet, ext::set < InputSymbolType > returnAlphabet, ext::set < InputSymbolType > localAlphabet, ext::set < PushdownStoreSymbolType > pushdownStoreAlphabet, ext::set < StateType > initialStates, PushdownStoreSymbolType bottomOfTheStackSymbol, ext::set < StateType > finalStates );
117
124 explicit VisiblyPushdownNPDA ( PushdownStoreSymbolType bottomOfTheStackSymbol );
125
132 return this->template accessComponent < InitialStates > ( ).get ( );
133 }
134
141 return std::move ( this->template accessComponent < InitialStates > ( ).get ( ) );
142 }
143
151 bool addInitialState ( StateType state ) {
152 return this->template accessComponent < InitialStates > ( ).add ( std::move ( state ) );
153 }
154
161 this->template accessComponent < InitialStates > ( ).set ( std::move ( states ) );
162 }
163
171 bool removeInitialState ( const StateType & state ) {
172 return this->template accessComponent < InitialStates > ( ).remove ( state );
173 }
174
180 const ext::set < StateType > & getStates ( ) const & {
181 return this-> template accessComponent < States > ( ).get ( );
182 }
183
190 return std::move ( this-> template accessComponent < States > ( ).get ( ) );
191 }
192
200 bool addState ( StateType state ) {
201 return this-> template accessComponent < States > ( ).add ( std::move ( state ) );
202 }
203
210 this-> template accessComponent < States > ( ).set ( std::move ( states ) );
211 }
212
220 bool removeState ( const StateType & state ) {
221 return this-> template accessComponent < States > ( ).remove ( state );
222 }
223
230 return this-> template accessComponent < FinalStates > ( ).get ( );
231 }
232
239 return std::move ( this-> template accessComponent < FinalStates > ( ).get ( ) );
240 }
241
249 bool addFinalState ( StateType state ) {
250 return this-> template accessComponent < FinalStates > ( ).add ( std::move ( state ) );
251 }
252
259 this-> template accessComponent < FinalStates > ( ).set ( std::move ( states ) );
260 }
261
269 bool removeFinalState ( const StateType & state ) {
270 return this-> template accessComponent < FinalStates > ( ).remove ( state );
271 }
272
279 return this->template accessComponent < PushdownStoreAlphabet > ( ).get ( );
280 }
281
288 return std::move ( this->template accessComponent < PushdownStoreAlphabet > ( ).get ( ) );
289 }
290
299 return this->template accessComponent < PushdownStoreAlphabet > ( ).add ( std::move ( symbol ) );
300 }
301
308 this->template accessComponent < PushdownStoreAlphabet > ( ).add ( std::move ( symbols ) );
309 }
310
317 this->template accessComponent < PushdownStoreAlphabet > ( ).set ( std::move ( symbols ) );
318 }
319
328 return this->template accessComponent < PushdownStoreAlphabet > ( ).remove ( symbol );
329 }
330
337 return this->template accessComponent < BottomOfTheStackSymbol > ( ).get ( );
338 }
339
346 return std::move ( this->template accessComponent < BottomOfTheStackSymbol > ( ).get ( ) );
347 }
348
357 return this->template accessComponent < BottomOfTheStackSymbol > ( ).set ( std::move ( symbol ) );
358 }
359
366 return this->template accessComponent < CallAlphabet > ( ).get ( );
367 }
368
375 return std::move ( this->template accessComponent < CallAlphabet > ( ).get ( ) );
376 }
377
386 return this->template accessComponent < CallAlphabet > ( ).add ( std::move ( symbol ) );
387 }
388
395 this->template accessComponent < CallAlphabet > ( ).add ( std::move ( symbols ) );
396 }
397
404 this->template accessComponent < CallAlphabet > ( ).set ( std::move ( symbols ) );
405 }
406
414 bool removeCallInputSymbol ( const InputSymbolType & symbol ) {
415 return this->template accessComponent < CallAlphabet > ( ).remove ( symbol );
416 }
417
424 return this->template accessComponent < ReturnAlphabet > ( ).get ( );
425 }
426
433 return std::move ( this->template accessComponent < ReturnAlphabet > ( ).get ( ) );
434 }
435
444 return this->template accessComponent < ReturnAlphabet > ( ).add ( std::move ( symbol ) );
445 }
446
453 this->template accessComponent < ReturnAlphabet > ( ).add ( std::move ( symbols ) );
454 }
455
462 this->template accessComponent < ReturnAlphabet > ( ).set ( std::move ( symbols ) );
463 }
464
472 bool removeReturnInputSymbol ( const InputSymbolType & symbol ) {
473 return this->template accessComponent < ReturnAlphabet > ( ).remove ( symbol );
474 }
475
482 return this->template accessComponent < LocalAlphabet > ( ).get ( );
483 }
484
491 return std::move ( this->template accessComponent < LocalAlphabet > ( ).get ( ) );
492 }
493
502 return this->template accessComponent < LocalAlphabet > ( ).add ( std::move ( symbol ) );
503 }
504
511 this->template accessComponent < LocalAlphabet > ( ).add ( std::move ( symbols ) );
512 }
513
520 this->template accessComponent < LocalAlphabet > ( ).set ( std::move ( symbols ) );
521 }
522
530 bool removeLocalInputSymbol ( const InputSymbolType & symbol ) {
531 return this->template accessComponent < LocalAlphabet > ( ).remove ( symbol );
532 }
533
541 bool removeInputSymbol(const InputSymbolType& symbol) {
542 return removeCallInputSymbol(symbol) || removeReturnInputSymbol(symbol) || removeLocalInputSymbol(symbol);
543 }
544
560
576
590 bool addLocalTransition ( StateType from, InputSymbolType input, StateType to );
591
606 bool removeCallTransition ( const StateType & from, const InputSymbolType & input, const StateType & to, const PushdownStoreSymbolType & push );
607
622 bool removeReturnTransition ( const StateType & from, const InputSymbolType & input, const PushdownStoreSymbolType & pop, const StateType & to );
623
637 bool removeLocalTransition ( const StateType & from, const InputSymbolType & input, const StateType & to );
638
645
651 ext::multimap < ext::pair < StateType, InputSymbolType >, ext::pair < StateType, PushdownStoreSymbolType > > && getCallTransitions ( ) &&;
652
658 const ext::multimap < ext::tuple < StateType, InputSymbolType, PushdownStoreSymbolType >, StateType > & getReturnTransitions ( ) const &;
659
666
672 const ext::multimap < ext::pair < StateType, InputSymbolType >, StateType > & getLocalTransitions ( ) const &;
673
679 ext::multimap < ext::pair < StateType, InputSymbolType >, StateType > && getLocalTransitions ( ) &&;
680
688 auto operator <=> ( const VisiblyPushdownNPDA & other ) const {
689 return std::tie(getStates(), getCallInputAlphabet(), getReturnInputAlphabet(), getLocalInputAlphabet(), getInitialStates(), getFinalStates(), getPushdownStoreAlphabet(), getBottomOfTheStackSymbol(), callTransitions, returnTransitions, localTransitions) <=> std::tie(other.getStates(), other.getCallInputAlphabet(), other.getReturnInputAlphabet(), other.getLocalInputAlphabet(), other.getInitialStates(), other.getFinalStates(), other.getPushdownStoreAlphabet(), other.getBottomOfTheStackSymbol(), other.callTransitions, other.returnTransitions, other.localTransitions);
690 }
691
699 bool operator == ( const VisiblyPushdownNPDA & other ) const {
700 return std::tie(getStates(), getCallInputAlphabet(), getReturnInputAlphabet(), getLocalInputAlphabet(), getInitialStates(), getFinalStates(), getPushdownStoreAlphabet(), getBottomOfTheStackSymbol(), callTransitions, returnTransitions, localTransitions) == std::tie(other.getStates(), other.getCallInputAlphabet(), other.getReturnInputAlphabet(), other.getLocalInputAlphabet(), other.getInitialStates(), other.getFinalStates(), other.getPushdownStoreAlphabet(), other.getBottomOfTheStackSymbol(), other.callTransitions, other.returnTransitions, other.localTransitions);
701 }
702
711 friend ext::ostream & operator << ( ext::ostream & out, const VisiblyPushdownNPDA & instance ) {
712 return out << "(VisiblyPushdownNPDA"
713 << " states = " << instance.getStates ( )
714 << " callAlphabet = " << instance.getCallInputAlphabet ( )
715 << " returnAlphabet = " << instance.getReturnInputAlphabet ( )
716 << " localAlphabet = " << instance.getLocalInputAlphabet ( )
717 << " initialStates = " << instance.getInitialStates ( )
718 << " finalStates = " << instance.getFinalStates ( )
719 << " pushdownStoreAlphabet = " << instance.getPushdownStoreAlphabet ( )
720 << " bottomOfTheStackSymbol = " << instance.getBottomOfTheStackSymbol ( )
721 << " callTransitions = " << instance.getCallTransitions ( )
722 << " returnTransitions = " << instance.getReturnTransitions ( )
723 << " localTransitions = " << instance.getLocalTransitions ( )
724 << ")";
725 }
726};
727
728template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
729VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >::VisiblyPushdownNPDA ( ext::set < StateType > states, ext::set < InputSymbolType > callAlphabet, ext::set < InputSymbolType > returnAlphabet, ext::set < InputSymbolType > localAlphabet, ext::set < PushdownStoreSymbolType > pushdownStoreAlphabet, ext::set < StateType > initialStates, PushdownStoreSymbolType bottomOfTheStackSymbol, ext::set < StateType > finalStates ) : core::Components < VisiblyPushdownNPDA, ext::set < InputSymbolType >, component::Set, std::tuple < CallAlphabet, ReturnAlphabet, LocalAlphabet >, ext::set < PushdownStoreSymbolType >, component::Set, PushdownStoreAlphabet, PushdownStoreSymbolType, component::Value, BottomOfTheStackSymbol, ext::set < StateType >, component::Set, std::tuple < States, InitialStates, FinalStates > > ( std::move ( callAlphabet ), std::move ( returnAlphabet ), std::move ( localAlphabet ), std::move ( pushdownStoreAlphabet ), std::move ( bottomOfTheStackSymbol ), std::move ( states ), std::move ( initialStates ), std::move ( finalStates ) ) {
730}
731
732template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
734}
735
736template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
738 if ( ! getStates().count(from)) {
739 throw AutomatonException("State \"" + ext::to_string ( from ) + "\" doesn't exist.");
740 }
741
742 if ( ! getCallInputAlphabet().count(input)) {
743 throw AutomatonException("Input symbol \"" + ext::to_string ( input ) + "\" doesn't exist.");
744 }
745
746 if ( ! getStates().count(to)) {
747 throw AutomatonException("State \"" + ext::to_string ( to ) + "\" doesn't exist.");
748 }
749
750 if (! getPushdownStoreAlphabet().count(push)) {
751 throw AutomatonException("Pushdown store symbol \"" + ext::to_string ( push ) + "\" doesn't exist.");
752 }
753
754 auto upper_bound = callTransitions.upper_bound ( ext::tie ( from, input ) );
755 auto lower_bound = callTransitions.lower_bound ( ext::tie ( from, input ) );
756
757 ext::pair < StateType, PushdownStoreSymbolType > value = ext::make_pair ( std::move ( to ), std::move ( push ) );
758
759 auto iter = std::lower_bound ( lower_bound, upper_bound, value, [ ] ( const auto & transition, const auto & target ) { return transition.second < target; } );
760 if ( iter != upper_bound && value >= iter->second )
761 return false;
762
763 ext::pair < StateType, InputSymbolType > key ( std::move ( from ), std::move ( input ) );
764
765 callTransitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( value ) ) );
766 return true;
767}
768
769template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
771 if (! getStates().count(from)) {
772 throw AutomatonException("State \"" + ext::to_string ( from ) + "\" doesn't exist.");
773 }
774
775 if (! getReturnInputAlphabet().count(input)) {
776 throw AutomatonException("Input symbol \"" + ext::to_string ( input ) + "\" doesn't exist.");
777 }
778
779 if (! getStates().count(to)) {
780 throw AutomatonException("State \"" + ext::to_string ( to ) + "\" doesn't exist.");
781 }
782
783 if (! getPushdownStoreAlphabet().count(pop)) {
784 throw AutomatonException("Pushdown store symbol \"" + ext::to_string ( pop ) + "\" doesn't exist.");
785 }
786
787 auto upper_bound = returnTransitions.upper_bound ( ext::tie ( from, input, pop ) );
788 auto lower_bound = returnTransitions.lower_bound ( ext::tie ( from, input, pop ) );
789
790 auto iter = std::lower_bound ( lower_bound, upper_bound, to, [ ] ( const auto & transition, const auto & target ) { return transition.second < target; } );
791 if ( iter != upper_bound && to >= iter->second )
792 return false;
793
794 ext::tuple < StateType, InputSymbolType, PushdownStoreSymbolType > key ( std::move ( from ), std::move ( input ), std::move ( pop ) );
795
796 returnTransitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( to ) ) );
797 return true;
798}
799
800template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
802 if (! getStates().count(from)) {
803 throw AutomatonException("State \"" + ext::to_string ( from ) + "\" doesn't exist.");
804 }
805
806 if (! getLocalInputAlphabet().count(input)) {
807 throw AutomatonException("Input symbol \"" + ext::to_string ( input ) + "\" doesn't exist.");
808 }
809
810 if (! getStates().count(to)) {
811 throw AutomatonException("State \"" + ext::to_string ( to ) + "\" doesn't exist.");
812 }
813
814 auto upper_bound = localTransitions.upper_bound ( ext::tie ( from, input ) );
815 auto lower_bound = localTransitions.lower_bound ( ext::tie ( from, input ) );
816
817 auto iter = std::lower_bound ( lower_bound, upper_bound, to, [ ] ( const auto & transition, const auto & target ) { return transition.second < target; } );
818 if ( iter != upper_bound && to >= iter->second )
819 return false;
820
821 ext::pair < StateType, InputSymbolType > key ( std::move ( from ), std::move ( input ) );
822
823 localTransitions.insert ( iter, std::make_pair ( std::move ( key ), std::move ( to ) ) );
824 return true;
825}
826
827template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
829 auto upper_bound = callTransitions.upper_bound ( ext::tie ( from, input ) );
830 auto lower_bound = callTransitions.lower_bound ( ext::tie ( from, input ) );
831 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] ( const auto & transition ) { return transition.second.first == to && transition.second.second == push; } );
832 if ( iter == upper_bound )
833 return false;
834
835 callTransitions.erase ( iter );
836 return true;
837}
838
839template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
841 auto upper_bound = returnTransitions.upper_bound ( ext::tie ( from, input, pop ) );
842 auto lower_bound = returnTransitions.lower_bound ( ext::tie ( from, input, pop ) );
843 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] ( const auto & transition ) { return transition.second == to; } );
844 if ( iter == upper_bound )
845 return false;
846
847 returnTransitions.erase ( iter );
848 return true;
849}
850
851template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
853 auto upper_bound = localTransitions.upper_bound ( ext::tie ( from, input ) );
854 auto lower_bound = localTransitions.lower_bound ( ext::tie ( from, input ) );
855 auto iter = std::find_if ( lower_bound, upper_bound, [ & ] ( const auto & transition ) { return transition.second == to; } );
856 if ( iter == upper_bound )
857 return false;
858
859 localTransitions.erase ( iter );
860 return true;
861}
862
863template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
865 return callTransitions;
866}
867
868template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
870 return std::move ( callTransitions );
871}
872
873template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
875 return returnTransitions;
876}
877
878template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
880 return std::move ( returnTransitions );
881}
882
883template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
885 return localTransitions;
886}
887
888template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
890 return std::move ( localTransitions );
891}
892
893} /* namespace automaton */
894
895namespace core {
896
904template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
905class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, InputSymbolType, automaton::CallAlphabet > {
906public:
916 for ( const std::pair<const ext::pair<StateType, InputSymbolType>, ext::pair < StateType, PushdownStoreSymbolType > > & callTransition : automaton.getCallTransitions())
917 if ( symbol == callTransition.first.second )
918 return true;
919
920 return false;
921 }
922
932 return true;
933 }
934
942 if(automaton.getLocalInputAlphabet().count(symbol))
943 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in local alphabet");
944 if(automaton.getReturnInputAlphabet().count(symbol))
945 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in return alphabet");
946 }
947};
948
956template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
957class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, InputSymbolType, automaton::ReturnAlphabet > {
958public:
968 for ( const std::pair < const ext::tuple<StateType, InputSymbolType, PushdownStoreSymbolType>, StateType > & returnTransition : automaton.getReturnTransitions ( ) )
969 if (symbol == std::get<1>(returnTransition.first))
970 return true;
971
972 return false;
973 }
974
984 return true;
985 }
986
994 if(automaton.getLocalInputAlphabet().count(symbol))
995 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in local alphabet");
996 if(automaton.getCallInputAlphabet().count(symbol))
997 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in call alphabet");
998 }
999};
1000
1008template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1009class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, InputSymbolType, automaton::LocalAlphabet > {
1010public:
1020 for ( const std::pair<const ext::pair<StateType, InputSymbolType>, StateType > & localTransition : automaton.getLocalTransitions ( ) )
1021 if (symbol == localTransition.first.second)
1022 return true;
1023
1024 return false;
1025 }
1026
1036 return true;
1037 }
1038
1046 if(automaton.getReturnInputAlphabet().count(symbol))
1047 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in return alphabet");
1048 if(automaton.getCallInputAlphabet().count(symbol))
1049 throw automaton::AutomatonException("Input symbol " + ext::to_string ( symbol ) + " already in call alphabet");
1050 }
1051};
1052
1060template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1061class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, PushdownStoreSymbolType, automaton::PushdownStoreAlphabet > {
1062public:
1072 for ( const std::pair<const ext::pair<StateType, InputSymbolType>, ext::pair < StateType, PushdownStoreSymbolType > > & transition : automaton.getCallTransitions ( ) )
1073 if (symbol == transition.second.second)
1074 return true;
1075
1076 for ( const std::pair<const ext::tuple<StateType, InputSymbolType, PushdownStoreSymbolType>, StateType > & returnTransition : automaton.getReturnTransitions ( ) )
1077 if (symbol == std::get<2>(returnTransition.first))
1078 return true;
1079
1080 if(automaton.getBottomOfTheStackSymbol() == symbol)
1081 return true;
1082
1083 return false;
1084 }
1085
1095 return true;
1096 }
1097
1105 }
1106};
1107
1115template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1116class ElementConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, PushdownStoreSymbolType, automaton::BottomOfTheStackSymbol > {
1117public:
1127 return automaton.template accessComponent < automaton::PushdownStoreAlphabet > ( ).get ( ).count ( symbol );
1128 }
1129
1137 }
1138};
1139
1147template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1148class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, StateType, automaton::States > {
1149public:
1159 if ( automaton.getInitialStates ( ).count ( state ) )
1160 return true;
1161
1162 if ( automaton.getFinalStates ( ).count ( state ) )
1163 return true;
1164
1165 for ( const std::pair<const ext::pair<StateType, InputSymbolType>, ext::pair < StateType, PushdownStoreSymbolType > > & transition : automaton.getCallTransitions()) {
1166 if ( state == transition.first.first )
1167 return true;
1168 if ( transition.second.first == state )
1169 return true;
1170 }
1171
1172 for ( const std::pair<const ext::tuple<StateType, InputSymbolType, PushdownStoreSymbolType>, StateType > & transition : automaton.getReturnTransitions()) {
1173 if (state == std::get<0>(transition.first))
1174 return true;
1175 if ( transition.second == state )
1176 return true;
1177 }
1178
1179 for ( const std::pair<const ext::pair<StateType, InputSymbolType>, StateType >& transition : automaton.getLocalTransitions()) {
1180 if (state == transition.first.first)
1181 return true;
1182 if ( transition.second == state )
1183 return true;
1184 }
1185
1186 return false;
1187 }
1188
1198 return true;
1199 }
1200
1208 }
1209};
1210
1218template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1219class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, StateType, automaton::FinalStates > {
1220public:
1230 return false;
1231 }
1232
1242 return automaton.template accessComponent < automaton::States > ( ).get ( ).count ( state );
1243 }
1244
1252 }
1253};
1254
1262template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1263class SetConstraint< automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType >, StateType, automaton::InitialStates > {
1264public:
1274 return false;
1275 }
1276
1286 return automaton.template accessComponent < automaton::States > ( ).get ( ).count ( state );
1287 }
1288
1296 }
1297};
1298
1304template < class InputSymbolType, class PushdownStoreSymbolType, class StateType >
1305struct normalize < automaton::VisiblyPushdownNPDA < InputSymbolType, PushdownStoreSymbolType, StateType > > {
1307 ext::set < DefaultSymbolType > call_alphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getCallInputAlphabet ( ) );
1308 ext::set < DefaultSymbolType > return_alphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getReturnInputAlphabet ( ) );
1309 ext::set < DefaultSymbolType > local_alphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getLocalInputAlphabet ( ) );
1310 ext::set < DefaultSymbolType > pushdownAlphabet = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getPushdownStoreAlphabet ( ) );
1311 DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getBottomOfTheStackSymbol ( ) );
1312 ext::set < DefaultStateType > states = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getStates ( ) );
1313 ext::set < DefaultStateType > initialStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getInitialStates ( ) );
1314 ext::set < DefaultStateType > finalStates = automaton::AutomatonNormalize::normalizeStates ( std::move ( value ).getFinalStates ( ) );
1315
1316 automaton::VisiblyPushdownNPDA < > res ( std::move ( states ), std::move ( call_alphabet ), std::move ( return_alphabet ), std::move ( local_alphabet ), std::move ( pushdownAlphabet ), std::move ( initialStates ), std::move ( initialSymbol ), std::move ( finalStates ) );
1317
1318 for ( std::pair < ext::pair < StateType, InputSymbolType >, ext::pair < StateType, PushdownStoreSymbolType > > && transition : ext::make_mover ( std::move ( value ).getCallTransitions ( ) ) ) {
1319 DefaultStateType to = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second.first ) );
1320 DefaultSymbolType push = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( transition.second.second ) );
1321
1322 DefaultStateType from = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.first.first ) );
1323 DefaultSymbolType input = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( transition.first.second ) );
1324
1325 res.addCallTransition ( std::move ( from ), std::move ( input ), std::move ( to ), std::move ( push ) );
1326 }
1327
1328 for ( std::pair < ext::tuple < StateType, InputSymbolType, PushdownStoreSymbolType >, StateType > && transition : ext::make_mover ( std::move ( value ).getReturnTransitions ( ) ) ) {
1329 DefaultStateType to = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
1330
1331 DefaultStateType from = automaton::AutomatonNormalize::normalizeState ( std::move ( std::get < 0 > ( transition.first ) ) );
1332 DefaultSymbolType input = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( std::get < 1 > ( transition.first ) ) );
1333 DefaultSymbolType pop = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( std::get < 2 > ( transition.first ) ) );
1334
1335 res.addReturnTransition ( std::move ( from ), std::move ( input ), std::move ( pop ), std::move ( to ) );
1336 }
1337
1338 for ( std::pair < ext::pair < StateType, InputSymbolType >, StateType > && transition : ext::make_mover ( std::move ( value ).getLocalTransitions ( ) ) ) {
1339 DefaultStateType to = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.second ) );
1340
1341 DefaultStateType from = automaton::AutomatonNormalize::normalizeState ( std::move ( transition.first.first ) );
1342 DefaultSymbolType input = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( transition.first.second ) );
1343
1344 res.addLocalTransition ( std::move ( from ), std::move ( input ), std::move ( to ) );
1345 }
1346
1347 return res;
1348 }
1349};
1350
1351} /* namespace core */
1352
1353extern template class automaton::VisiblyPushdownNPDA < >;
1354
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
Nondeterministic visibly pushdown automaton. Accepts subset of context free languages.
Definition: VisiblyPushdownNPDA.h:81
void setPushdownStoreAlphabet(ext::set< PushdownStoreSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:316
void setCallInputAlphabet(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:403
bool removeLocalInputSymbol(const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:530
VisiblyPushdownNPDA(ext::set< StateType > states, ext::set< InputSymbolType > callAlphabet, ext::set< InputSymbolType > returnAlphabet, ext::set< InputSymbolType > localAlphabet, ext::set< PushdownStoreSymbolType > pushdownStoreAlphabet, ext::set< StateType > initialStates, PushdownStoreSymbolType bottomOfTheStackSymbol, ext::set< StateType > finalStates)
Creates a new instance of the automaton with a concrete set of states, call, return,...
Definition: VisiblyPushdownNPDA.h:729
bool removeLocalTransition(const StateType &from, const InputSymbolType &input, const StateType &to)
Removes a local transition from the automaton.
Definition: VisiblyPushdownNPDA.h:852
bool addLocalTransition(StateType from, InputSymbolType input, StateType to)
Adds a local transition to the automaton.
Definition: VisiblyPushdownNPDA.h:801
ext::set< StateType > && getFinalStates() &&
Definition: VisiblyPushdownNPDA.h:238
const PushdownStoreSymbolType & getBottomOfTheStackSymbol() const &
Definition: VisiblyPushdownNPDA.h:336
const ext::set< StateType > & getInitialStates() const &
Definition: VisiblyPushdownNPDA.h:131
const ext::set< PushdownStoreSymbolType > & getPushdownStoreAlphabet() const &
Definition: VisiblyPushdownNPDA.h:278
bool removeReturnInputSymbol(const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:472
bool removePushdownStoreSymbol(const PushdownStoreSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:327
ext::set< InputSymbolType > && getReturnInputAlphabet() &&
Definition: VisiblyPushdownNPDA.h:432
bool removeState(const StateType &state)
Definition: VisiblyPushdownNPDA.h:220
bool addFinalState(StateType state)
Definition: VisiblyPushdownNPDA.h:249
StateTypeT StateType
Definition: VisiblyPushdownNPDA.h:85
const ext::set< StateType > & getStates() const &
Definition: VisiblyPushdownNPDA.h:180
bool addCallInputSymbol(InputSymbolType symbol)
Definition: VisiblyPushdownNPDA.h:385
bool addReturnTransition(StateType from, InputSymbolType input, PushdownStoreSymbolType pop, StateType to)
Adds a return transition to the automaton.
Definition: VisiblyPushdownNPDA.h:770
bool addReturnInputSymbol(InputSymbolType symbol)
Definition: VisiblyPushdownNPDA.h:443
bool operator==(const VisiblyPushdownNPDA &other) const
Definition: VisiblyPushdownNPDA.h:699
bool removeInputSymbol(const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:541
void setInitialStates(ext::set< StateType > states)
Definition: VisiblyPushdownNPDA.h:160
PushdownStoreSymbolTypeT PushdownStoreSymbolType
Definition: VisiblyPushdownNPDA.h:84
ext::set< InputSymbolType > && getCallInputAlphabet() &&
Definition: VisiblyPushdownNPDA.h:374
const ext::multimap< ext::pair< StateType, InputSymbolType >, StateType > & getLocalTransitions() const &
Definition: VisiblyPushdownNPDA.h:884
void addReturnInputSymbols(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:452
bool removeCallInputSymbol(const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:414
bool removeCallTransition(const StateType &from, const InputSymbolType &input, const StateType &to, const PushdownStoreSymbolType &push)
Removes a call transition from the automaton.
Definition: VisiblyPushdownNPDA.h:828
ext::set< InputSymbolType > && getLocalInputAlphabet() &&
Definition: VisiblyPushdownNPDA.h:490
void setFinalStates(ext::set< StateType > states)
Definition: VisiblyPushdownNPDA.h:258
void setReturnInputAlphabet(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:461
bool addCallTransition(StateType from, InputSymbolType input, StateType to, PushdownStoreSymbolType push)
Adds a call transition to the automaton.
Definition: VisiblyPushdownNPDA.h:737
bool removeInitialState(const StateType &state)
Definition: VisiblyPushdownNPDA.h:171
void setLocalInputAlphabet(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:519
friend ext::ostream & operator<<(ext::ostream &out, const VisiblyPushdownNPDA &instance)
Definition: VisiblyPushdownNPDA.h:711
InputSymbolTypeT InputSymbolType
Definition: VisiblyPushdownNPDA.h:83
bool addLocalInputSymbol(InputSymbolType symbol)
Definition: VisiblyPushdownNPDA.h:501
bool addInitialState(StateType state)
Definition: VisiblyPushdownNPDA.h:151
const ext::set< InputSymbolType > & getCallInputAlphabet() const &
Definition: VisiblyPushdownNPDA.h:365
ext::set< StateType > && getStates() &&
Definition: VisiblyPushdownNPDA.h:189
void addLocalInputSymbols(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:510
bool removeReturnTransition(const StateType &from, const InputSymbolType &input, const PushdownStoreSymbolType &pop, const StateType &to)
Removes a return transition from the automaton.
Definition: VisiblyPushdownNPDA.h:840
void addCallInputSymbols(ext::set< InputSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:394
ext::set< StateType > && getInitialStates() &&
Definition: VisiblyPushdownNPDA.h:140
const ext::set< StateType > & getFinalStates() const &
Definition: VisiblyPushdownNPDA.h:229
bool addState(StateType state)
Definition: VisiblyPushdownNPDA.h:200
void addPushdownStoreSymbols(ext::set< PushdownStoreSymbolType > symbols)
Definition: VisiblyPushdownNPDA.h:307
const ext::set< InputSymbolType > & getReturnInputAlphabet() const &
Definition: VisiblyPushdownNPDA.h:423
PushdownStoreSymbolType && getBottomOfTheStackSymbol() &&
Definition: VisiblyPushdownNPDA.h:345
ext::set< PushdownStoreSymbolType > && getPushdownStoreAlphabet() &&
Definition: VisiblyPushdownNPDA.h:287
const ext::multimap< ext::tuple< StateType, InputSymbolType, PushdownStoreSymbolType >, StateType > & getReturnTransitions() const &
Definition: VisiblyPushdownNPDA.h:874
bool removeFinalState(const StateType &state)
Definition: VisiblyPushdownNPDA.h:269
const ext::multimap< ext::pair< StateType, InputSymbolType >, ext::pair< StateType, PushdownStoreSymbolType > > & getCallTransitions() const &
Definition: VisiblyPushdownNPDA.h:864
void setStates(ext::set< StateType > states)
Definition: VisiblyPushdownNPDA.h:209
bool setBottomOfTheStackSymbol(PushdownStoreSymbolType symbol)
Definition: VisiblyPushdownNPDA.h:356
const ext::set< InputSymbolType > & getLocalInputAlphabet() const &
Definition: VisiblyPushdownNPDA.h:481
bool addPushdownStoreSymbol(PushdownStoreSymbolType symbol)
Definition: VisiblyPushdownNPDA.h:298
Definition: components.hpp:181
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const PushdownStoreSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:1126
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const PushdownStoreSymbolType &)
Definition: VisiblyPushdownNPDA.h:1136
Definition: components.hpp:25
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const InputSymbolType &)
Definition: VisiblyPushdownNPDA.h:931
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:941
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:915
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const InputSymbolType &)
Definition: VisiblyPushdownNPDA.h:1035
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:1019
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:1045
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const StateType &state)
Definition: VisiblyPushdownNPDA.h:1241
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1229
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1251
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1197
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1207
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const StateType &state)
Definition: VisiblyPushdownNPDA.h:1158
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:993
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const InputSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:967
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const InputSymbolType &)
Definition: VisiblyPushdownNPDA.h:983
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const PushdownStoreSymbolType &)
Definition: VisiblyPushdownNPDA.h:1104
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const PushdownStoreSymbolType &symbol)
Definition: VisiblyPushdownNPDA.h:1071
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const PushdownStoreSymbolType &)
Definition: VisiblyPushdownNPDA.h:1094
static bool available(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &automaton, const StateType &state)
Definition: VisiblyPushdownNPDA.h:1285
static void valid(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1295
static bool used(const automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &, const StateType &)
Definition: VisiblyPushdownNPDA.h:1273
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 tuple class from the standard library. Original reason is to allow printing of th...
Definition: tuple.hpp:42
Definition: Object.h:16
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return res
Definition: MinimizeByPartitioning.h:145
Definition: ToGrammar.h:31
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
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::VisiblyPushdownNPDA< > eval(automaton::VisiblyPushdownNPDA< InputSymbolType, PushdownStoreSymbolType, StateType > &&value)
Definition: VisiblyPushdownNPDA.h:1306
Definition: normalize.hpp:13