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
SingleInitialState.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 <ext/algorithm>
27
28#include <alib/set>
29
30#include <automaton/FSM/DFA.h>
31#include <automaton/FSM/NFA.h>
37
40
41namespace automaton {
42
43namespace simplify {
44
52 template < class T >
53 struct NFATra {
55 };
56
57 template < class T >
58 struct EpsilonNFATra {
60 };
61
62 template < class T >
63 using ConvertedAutomaton = typename ext::casional <
66 >::type::type;
67
68public:
78 template < class T >
79 requires isMultiInitialStateNFA < T > || isMultiInitialStateEpsilonNFA < T >
80 static SingleInitialState::ConvertedAutomaton < T > convert ( const T & fsm );
81
85 template < class T >
86 requires isDFA < T > || isNFA < T > || isEpsilonNFA < T > || isExtendedNFA < T > || isCompactNFA < T >
87 static T convert ( const T & fsm );
88};
89
90template < class T >
91requires isMultiInitialStateNFA < T > || isMultiInitialStateEpsilonNFA < T >
92SingleInitialState::ConvertedAutomaton < T > SingleInitialState::convert ( const T & fsm ) {
93 using StateType = typename T::StateType;
94
95 // step 1, 3
96 StateType q0 = common::createUnique ( label::InitialStateLabel::instance < StateType > ( ), fsm.getStates ( ) );
97
98 SingleInitialState::ConvertedAutomaton < T > res ( q0 );
99 res.setInputAlphabet ( fsm.getInputAlphabet ( ) );
100
101 for( const StateType & q : fsm.getStates ( ) )
102 res.addState ( q );
103
104 // step 2
105 for ( const auto & q : fsm.getInitialStates ( ) )
106 for(const auto & kv : fsm.getTransitionsFromState ( q ) )
107 res.addTransition ( q0, kv.first.second, kv.second );
108
109 for ( const auto & t : fsm.getTransitions ( ) )
110 res.addTransition ( t.first.first, t.first.second, t.second );
111
112 res.setFinalStates ( fsm.getFinalStates ( ) );
113
114 // step 4, 5
115 if ( ! ext::excludes ( fsm.getFinalStates ( ).begin ( ), fsm.getFinalStates ( ).end ( ), fsm.getInitialStates ( ).begin ( ), fsm.getInitialStates ( ).end ( ) ) )
116 res.addFinalState ( q0 );
117
118 return res;
119}
120
121template < class T >
122requires isDFA < T > || isNFA < T > || isEpsilonNFA < T > || isExtendedNFA < T > || isCompactNFA < T >
123T SingleInitialState::convert ( const T & fsm ) {
124 return fsm;
125}
126
127} /* namespace simplify */
128
129} /* namespace automaton */
130
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
Definition: SingleInitialState.h:51
static SingleInitialState::ConvertedAutomaton< T > convert(const T &fsm)
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return res
Definition: MinimizeByPartitioning.h:145
q
Definition: SingleInitialStateEpsilonTransition.h:85
StateType q0
Definition: SingleInitialState.h:96
Definition: ToGrammar.h:31
T createUnique(T object, const Alphabets &... alphabets)
Definition: createUnique.hpp:46
bool excludes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp)
Tests two sorted ranges wheter all elements from the second are not present in the first.
Definition: algorithm.hpp:46
typename std::conditional< value, std::true_type, std::false_type >::type boolean
Definition: type_traits.hpp:145
Definition: type_traits.hpp:148