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
RandomAutomatonFactory.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#include <ext/random>
28
29#include <alib/deque>
30#include <alib/set>
31#include <alib/string>
32
34
35#include <automaton/FSM/NFA.h>
36
37namespace automaton {
38
39namespace generate {
40
48public:
59 template < class SymbolType >
60 static automaton::NFA < SymbolType, unsigned > generateNFA ( size_t statesCount, const ext::set < SymbolType > & alphabet, double density );
61
74 static automaton::NFA < std::string, unsigned > generateNFA ( size_t statesCount, size_t alphabetSize, bool randomizedAlphabet, double density );
75
76private:
85 static unsigned ithAccessibleState ( const ext::deque < bool > & VStates, size_t i );
86
95 static unsigned ithInaccessibleState ( const ext::deque < bool > & VStates, size_t i );
96
108 template < class SymbolType >
109 static automaton::NFA < SymbolType, unsigned > LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density );
110};
111
112template < class SymbolType >
114 ext::deque < SymbolType > alphabet2 ( alphabet.begin ( ), alphabet.end ( ) );
115 return RandomAutomatonFactory::LeslieConnectedNFA ( statesCount, alphabet2, density );
116}
117
118template < class SymbolType >
119automaton::NFA < SymbolType, unsigned > RandomAutomatonFactory::LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density ) {
120 if( alphabet.empty ( ) )
121 throw exception::CommonException( "Alphabet size must be greater than 0." );
122
123 ext::deque<bool> VStates;
125 size_t unvisited;
126
128
129 for( const auto & s : alphabet )
130 automaton.addInputSymbol( s );
131
132 for( size_t i = 0; i < n; i ++ ) {
133 VStates.push_back( false );
134 Q.push_back( i );
135 automaton.addState( Q[ i ] );
136 }
137
138 if( n == 0 ) {
139 return automaton;
140 } else if( n == 1 ) {
141 automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ 0 ] );
142
143 unvisited = 0;
144 VStates[ 0 ] = true;
145 } else {
146 unsigned x = ( ext::random_devices::semirandom() % ( n - 1 ) ) + 1;
147 automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ x ] );
148 unvisited = n - 2;
149
150 VStates[ 0 ] = true;
151 VStates[ x ] = true;
152 }
153
154 while( unvisited != 0 ) {
155 size_t a = ithAccessibleState ( VStates, ext::random_devices::semirandom() % ( n - unvisited ) ); // select y-th accessible state
156 size_t b = ithInaccessibleState ( VStates, ext::random_devices::semirandom() % unvisited ); // select z-th inaccessible state
157
158 int c = ext::random_devices::semirandom() % alphabet.size( );
159 automaton.addTransition( Q[ a ], alphabet[ c ], Q[ b ] );
160
161 unvisited -= 1;
162 VStates[ b ] = true;
163 }
164
165 for( const unsigned & q : Q ) {
166 if( automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 90 )
167 automaton.addFinalState( q );
168 else if( !automaton.getTransitionsFromState( q ).empty ( ) && ext::random_devices::semirandom() % 100 < 10 )
169 automaton.addFinalState( q );
170 }
171
172 if( automaton.getFinalStates( ).empty ( ) ) {
173 if( n == 1 ) {
174 automaton.addFinalState( automaton.getInitialState( ) );
175 } else {
176 for( const unsigned & q : Q ) {
177 if( automaton.getTransitionsFromState( q ).empty ( ) ) {
178 automaton.addFinalState( q );
179 break;
180 }
181 }
182 }
183 }
184
185 double mnn100 = 100.0 / alphabet.size( ) / n / n;
186 while( automaton.getTransitions ( ).size ( ) * mnn100 < density ) {
189 int a = ext::random_devices::semirandom() % alphabet.size();
190
191 automaton.addTransition( Q[ y ], alphabet [ a ], Q[ z ] );
192 }
193
194 ext::set < SymbolType > alphabetUsage = automaton.getInputAlphabet ( );
195 for ( const auto & t : automaton.getTransitions ( ) )
196 alphabetUsage.erase ( t.first.second );
197
198 for ( const auto & kv : alphabetUsage )
199 automaton.removeInputSymbol ( kv );
200
201 return automaton;
202}
203
204} /* namespace generate */
205
206} /* namespace automaton */
207
Nondeterministic finite automaton. Accepts regular languages.
Definition: NFA.h:66
Definition: RandomAutomatonFactory.h:47
static automaton::NFA< SymbolType, unsigned > generateNFA(size_t statesCount, const ext::set< SymbolType > &alphabet, double density)
Definition: RandomAutomatonFactory.h:113
Basic exception from which all other exceptions are derived.
Definition: CommonException.h:21
Class extending the deque class from the standard library. Original reason is to allow printing of th...
Definition: deque.hpp:44
static semirandom_device & semirandom
The reference to singleton semirandom device.
Definition: random.hpp:147
Definition: set.hpp:44
Definition: BarSymbol.cpp:12
int i
Definition: AllEpsilonClosure.h:118
q
Definition: SingleInitialStateEpsilonTransition.h:85
Definition: ToGrammar.h:31