Newer
Older
* This file is part of Algorithms library toolkit.
* Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
* Algorithms library toolkit is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
* Algorithms library toolkit is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with Algorithms library toolkit. If not, see <http://www.gnu.org/licenses/>.
*
*/
#ifndef RANDOM_AUTOMATON_FACTORY_H_
#define RANDOM_AUTOMATON_FACTORY_H_
#include <alib/algorithm>
#include <alib/random>
#include <exception/CommonException.h>
namespace automaton {
namespace generate {
/**
* Generator of random automata.
*
* The underlying generation algorithm is from Leslie, T: Efficient Approaches to Subset Construction, 1995.
*/
/**
* Generates a random finite automaton.
* \tparam SymbolType the type of terminal symbols of the random automaton
*
* \param statesCount number of states in the generated automaton
* \param alphabet Input alphabet of the automaton
* \param density density of the transition function
*
* \return random nondeterministic finite automaton
template < class SymbolType >
static automaton::NFA < SymbolType, unsigned > generateNFA ( size_t statesCount, const ext::set < SymbolType > & alphabet, double density );
/**
* \overload
*
* Generates a random finite automaton.
*
* \param statesCount number of states in the generated automaton
* \param alphabetSize size of the alphabet (1-26)
* \param randomizedAlphabet selects random symbols from a-z range if true
* \param density density of the transition function (0-1). 1 means every possible transition is created
*
* \return random nondeterministic finite automaton
static automaton::NFA < char, unsigned > generateNFA ( size_t statesCount, size_t alphabetSize, bool randomizedAlphabet, double density );
/**
* Selects ith accessible state form \p VStates.
*
* \param VStates the states to select from
* \param i the specification which accessble state to select
*
* \return ith accessible state based on VStates
*/
static unsigned ithAccessibleState ( const ext::deque < bool > & VStates, size_t i );
/**
* Selects ith inaccessible state form \p VStates.
*
* \param VStates the states to select from
* \param i the specification which inaccessble state to select
*
* \return ith inaccessible state based on VStates
*/
static unsigned ithInaccessibleState ( const ext::deque < bool > & VStates, size_t i );
/**
* Leslie's connected NFA algorithm
*
* \tparam SymbolType the type of terminal symbols of the random automaton
*
* \param n number of states
* \param alphabet input alphabet
* \param density density of the transition function (0-1). 1 means every possible transition is created
*
* \return the actual random nondeterministic automaton
template < class SymbolType >
static automaton::NFA < SymbolType, unsigned > LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density );
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
template < class SymbolType >
automaton::NFA < SymbolType, unsigned > RandomAutomatonFactory::generateNFA ( size_t statesCount, const ext::set < SymbolType > & alphabet, double density ) {
ext::deque < SymbolType > alphabet2 ( alphabet.begin ( ), alphabet.end ( ) );
return RandomAutomatonFactory::LeslieConnectedNFA ( statesCount, alphabet2, density );
}
template < class SymbolType >
automaton::NFA < SymbolType, unsigned > RandomAutomatonFactory::LeslieConnectedNFA ( size_t n, const ext::deque < SymbolType > & alphabet, double density ) {
if( alphabet.size( ) <= 0 )
throw exception::CommonException( "Alphabet size must be greater than 0." );
ext::deque<bool> VStates;
ext::deque<unsigned> Q;
int unvisited;
automaton::NFA < SymbolType, unsigned > automaton( 0 );
for( const auto & s : alphabet )
automaton.addInputSymbol( s );
for( size_t i = 0; i < n; i ++ ) {
VStates.push_back( false );
Q.push_back( i );
automaton.addState( Q[ i ] );
}
if( n == 0 ) {
return automaton;
} else if( n == 1 ) {
automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ 0 ] );
unvisited = 0;
VStates[ 0 ] = true;
} else {
unsigned x = ( ext::random_devices::semirandom() % ( n - 1 ) ) + 1;
automaton.addTransition( Q[ 0 ], alphabet[ ext::random_devices::semirandom() % alphabet.size( ) ], Q[ x ] );
unvisited = n - 2;
VStates[ 0 ] = true;
VStates[ x ] = true;
}
while( unvisited != 0 ) {
size_t a = ithAccessibleState ( VStates, ext::random_devices::semirandom() % ( n - unvisited ) ); // select y-th accessible state
size_t b = ithInaccessibleState ( VStates, ext::random_devices::semirandom() % unvisited ); // select z-th inaccessible state
int c = ext::random_devices::semirandom() % alphabet.size( );
automaton.addTransition( Q[ a ], alphabet[ c ], Q[ b ] );
unvisited -= 1;
VStates[ b ] = true;
}
for( const unsigned & q : Q ) {
if( automaton.getTransitionsFromState( q ).size( ) == 0 && ext::random_devices::semirandom() % 100 < 90 )
automaton.addFinalState( q );
else if( automaton.getTransitionsFromState( q ).size( ) > 0 && ext::random_devices::semirandom() % 100 < 10 )
automaton.addFinalState( q );
}
if( automaton.getFinalStates( ).size( ) == 0 ) {
if( n == 1 ) {
automaton.addFinalState( automaton.getInitialState( ) );
} else {
for( const unsigned & q : Q ) {
if( automaton.getTransitionsFromState( q ).size( ) == 0 ) {
automaton.addFinalState( q );
break;
}
}
}
}
double mnn100 = 100.0 / alphabet.size( ) / n / n;
while( automaton.transitionsSize( ) * mnn100 < density ) {
int y = ext::random_devices::semirandom() % n;
int z = ext::random_devices::semirandom() % n;
int a = ext::random_devices::semirandom() % alphabet.size();
automaton.addTransition( Q[ y ], alphabet [ a ], Q[ z ] );
}
ext::map<SymbolType, bool> alphabetUsage;
for( const auto & a : automaton.getInputAlphabet( ) )
alphabetUsage[ a ] = false;
for( const auto & t : automaton.getTransitions( ) )
alphabetUsage[ t.first.second ] = true;
for( const auto & kv : alphabetUsage )
if( kv.second == false )
automaton.removeInputSymbol( kv.first );
return automaton;
}
} /* namespace generate */
} /* namespace automaton */