Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
EpsilonRemoverIncoming.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
28#include <automaton/FSM/NFA.h>
29#include <automaton/FSM/DFA.h>
30
32
33namespace automaton {
34
35namespace simplify {
36
44public:
53 template < class SymbolType, class StateType >
55
59 template < class SymbolType, class StateType >
61
67 template < class SymbolType, class StateType >
69
75 template < class SymbolType, class StateType >
77
78};
79
80template < class SymbolType, class StateType >
82 return fsm;
83}
84
85template < class SymbolType, class StateType >
87 return fsm;
88}
89
90template < class SymbolType, class StateType >
92 return fsm;
93}
94
95template < class SymbolType, class StateType >
98
99 res.setStates( fsm.getStates() );
100 res.setInputAlphabet( fsm.getInputAlphabet() );
101
103
107 for( const auto & from : fsm.getStates( ) )
108 for( const auto & fromClosure : automaton::properties::EpsilonClosure::epsilonClosure( fsm, from ) )
109 for( const auto & symbol : fsm.getInputAlphabet() )
110 for( const auto & transition : origTransitions.equal_range(ext::make_pair(fromClosure, symbol)) )
111 res.addTransition( from, symbol, transition.second );
112
116 const ext::set<StateType> & F = fsm.getFinalStates( );
117 for( const auto & q : res.getStates( ) ) {
119
120 if ( ! ext::excludes ( cl.begin(), cl.end(), F.begin(), F.end() ) )
121 res.addFinalState( q );
122 }
123
124 return res;
125}
126
127} /* namespace simplify */
128
129} /* namespace automaton */
130
Deterministic finite automaton. Accepts regular languages.
Definition: DFA.h:71
Epsilon nondeterministic finite automaton. Accepts regular languages.
Definition: EpsilonNFA.h:74
const ext::set< StateType > & getStates() const &
Definition: EpsilonNFA.h:158
const ext::set< StateType > & getFinalStates() const &
Definition: EpsilonNFA.h:207
const ext::set< SymbolType > & getInputAlphabet() const &
Definition: EpsilonNFA.h:256
ext::multimap< ext::pair< StateType, SymbolType >, StateType > getSymbolTransitions() const
Definition: EpsilonNFA.h:687
const StateType & getInitialState() const &
Definition: EpsilonNFA.h:129
Nondeterministic finite automaton with multiple initial states. Accepts regular languages.
Definition: MultiInitialStateNFA.h:69
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
static ext::set< StateType > epsilonClosure(const automaton::EpsilonNFA< SymbolType, StateType > &fsm, const StateType &q)
Definition: EpsilonClosure.h:125
Definition: EpsilonRemoverIncoming.h:43
static automaton::NFA< SymbolType, StateType > remove(const automaton::EpsilonNFA< SymbolType, StateType > &fsm)
Definition: EpsilonRemoverIncoming.h:96
Class extending the multimap class from the standard library. Original reason is to allow printing of...
Definition: multimap.hpp:48
auto equal_range(K &&key) const &
Make range of elements with key equal to the key.
Definition: multimap.hpp:268
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
typename T::StateType StateType
Definition: ToGrammarLeftRG.h:64
return res
Definition: MinimizeByPartitioning.h:145
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31
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
constexpr auto make_pair(T1 &&x, T2 &&y)
Definition: pair.hpp:79