Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
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