Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
NumberOfSymbolsAutomaton.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/set>
27#include <alib/string>
28
30
31#include <automaton/FSM/NFA.h>
32
33namespace automaton::generate {
34
39public:
51 template < class SymbolType >
52 static automaton::NFA < SymbolType, unsigned > generateNFA ( size_t modulo, const ext::set < SymbolType > & alphabet, SymbolType symbol, size_t final_modulo );
53
67 static automaton::NFA < std::string, unsigned > generateNFA ( size_t modulo, size_t alphabetSize, bool randomizedAlphabet, char symbol, size_t final_modulo );
68};
69
70template < class SymbolType >
72 if ( ! alphabet.contains ( symbol ) )
73 throw exception::CommonException ( "Symbol is not in the alphabet." );
74
76
77 automaton.setInputAlphabet ( alphabet );
78
79 for ( size_t i = 1; i < modulo; ++ i )
80 automaton.addState ( i );
81
82 for ( size_t i = 0; i < modulo; ++ i )
83 automaton.addTransition ( i, symbol, ( i + 1 ) % modulo );
84
85 for ( size_t i = 0; i < modulo; ++ i )
86 for ( const SymbolType & alphabet_symbol : alphabet )
87 if ( alphabet_symbol != symbol )
88 automaton.addTransition ( i, alphabet_symbol, i );
89
90 automaton.addFinalState ( final_modulo );
91
92 return automaton;
93}
94
95} /* namespace automaton::generate */
96
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
Definition: NumberOfSymbolsAutomaton.h:38
static automaton::NFA< SymbolType, unsigned > generateNFA(size_t modulo, const ext::set< SymbolType > &alphabet, SymbolType symbol, size_t final_modulo)
Definition: NumberOfSymbolsAutomaton.h:71
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
Definition: set.hpp:44
Definition: BarSymbol.cpp:12
Definition: NumberModuloAutomaton.cpp:10
int i
Definition: AllEpsilonClosure.h:118
typename T::SymbolType SymbolType
Definition: ReachableStates.h:176
Definition: ToGrammar.h:31