diff options
Diffstat (limited to 'semestr-6/jfizo/rozwy/gen.cpp')
| -rw-r--r-- | semestr-6/jfizo/rozwy/gen.cpp | 244 |
1 files changed, 244 insertions, 0 deletions
diff --git a/semestr-6/jfizo/rozwy/gen.cpp b/semestr-6/jfizo/rozwy/gen.cpp new file mode 100644 index 0000000..a6a2988 --- /dev/null +++ b/semestr-6/jfizo/rozwy/gen.cpp @@ -0,0 +1,244 @@ +#include <iostream> +#include <vector> +#include <assert.h> +#include <unordered_map> +#include <string> +#include <algorithm> + +using namespace std; + +typedef vector<int> transitions; +typedef vector<int> word; + +struct Automaton { + int states; + vector<int> accept; + vector<transitions> delta; + int initial; + + Automaton(int in, int n, const vector<transitions> &d, const vector<int> &acc) { + assert(in < n); + assert(d.size() == n); + + accept = acc; + delta.resize(n); + for (int i = 0; i < d.size(); i++) { + delta[i] = transitions(d[i]); + } + in = initial; + states = n; + } + + int apply(const word &w, int beg) { + int crawl = beg; + for (auto c: w) { + crawl = delta[crawl][c]; + } + return crawl; + } + + bool check(const word &s) { + int q = apply(s, initial); + for (auto i: accept) { + if (q == i) + return true; + } + return false; + } + + void dump() { + cout << "States: " << states << "; accepting: "; + for (auto i: accept) cout << i << " "; + cout << "\n"; + cout << "Transition table:\n"; + for (int i = 0; i < states; i++) { + cout << i << ":"; + for (int j = 0; j < delta[i].size(); j++) { + cout << "\t--" << (char)(j + 'a') << "--> " << delta[i][j] << "\n"; + } + } + } +}; + +void fill_accepts(int mask, int states, vector<int> &acc) { + acc.clear(); + for (int i = 0; i < states; i++) { + if (mask & (1<<i)) + acc.push_back(1); + else + acc.push_back(0); + } +} + +bool nextperm(int states, transitions &t, int alph_sz) { + for (int s = 0; s < alph_sz; s++) { + t[s]++; + if (t[s] == states) { + t[s] = 0; + } + else { + return true; + } + } + return false; +} + +void reset_transition(transitions &t, int alph_sz) { + for (int s = 0; s < alph_sz; s++) { + t[s] = 0; + } +} + +bool next_word(word &w, int alph_sz) { + for (int i = 0; i < w.size(); i++) { + w[i]++; + if (w[i] == alph_sz) { + w[i] = 0; + } else return true; + } + return false; +} + +vector<word> generate_words(int max_len, int alph_sz) { + vector<word> result; + for (int len = 0; len <= max_len; len++) { + word w; + for (int i = 0; i < len; i++) w.push_back(0); + do { + result.push_back(w); + } while (next_word(w, alph_sz)); + } + return result; +} + +void get_transitions(Automaton &aut, word &w, vector<int> &res) { + res.clear(); + for (int i = 0; i < aut.states; i++) { + res.push_back(aut.apply(w, i)); + } +} + +int my_power(int a, int b) { + if (b == 0) return 1; + return a * my_power(a, b-1); +} + +bool check_automaton(vector<word> &words, Automaton &aut) { + vector<vector<int>> funcs; + for (auto w: words) { + vector<int> trans; + get_transitions(aut, w, trans); + funcs.push_back(trans); + } + sort(funcs.begin(), funcs.end()); + auto it = unique(funcs.begin(), funcs.end()); + funcs.erase(it, funcs.end()); + + cout << funcs.size() << "\n"; + if (funcs.size() == my_power(aut.states, aut.states)) { + cout << "mamy to!!\n"; + aut.dump(); + return true; + } + return false; +} + +vector<Automaton> generate_automatons(int states, int alph_sz, vector<word> &words) { + vector<Automaton> result; + vector<transitions> delta; + vector<int> accepts; + + for (int i = 0; i < states; i++) { + delta.push_back(transitions()); + for (int s = 0; s < alph_sz; s++) { + delta[i].push_back(0); + } + } + + /* loop over accepting states */ + // for (int i = 0; i < (1<<states); i++) { + // if (i == 0) continue; + fill_accepts(1, states, accepts); + + /* loop over possible transitions */ + bool last = false; + while (!last) { + Automaton a(0, states, delta, accepts); + if (check_automaton(words, a)) { + return result; + } + // result.push_back(a); + last = true; + for (int i = 0; i < states; i++) { + if (nextperm(states, delta[i], alph_sz)) { + last = false; + break; + } + else { + reset_transition(delta[i], alph_sz); + } + } + } + // } + + return result; +} + +Automaton automaton_from_input() { + int states, alph_sz; + cin >> states >> alph_sz; + + vector<int> accept; + vector<transitions> delta; + int initial; + + fill_accepts(1, states, accept); + + initial = 0; + for (int i = 0; i < states; i++) { + cout << i << ":"; + delta.push_back(transitions()); + for (int j = 0; j < alph_sz; j++) { + int x; + cout << "\t--" << (char)(j + 'a') << "--> ? "; + cin >> x; + delta[i].push_back(x); + } + } + + return Automaton(0, states, delta, accept); +} + +int main(int argc, char *argv[]) { + if (argc != 4) { + fprintf(stderr, "Usage: %s states alph_sz word_sz\n", argv[0]); + return -1; + } + + int states = atoi(argv[1]); + int alph_sz = atoi(argv[2]); + int word_sz = atoi(argv[3]); + + + // vector<Automaton> automatons = generate_automatons(states, alph_sz); + + // for (auto a: automatons) { + // a.dump(); + // cout << "\n"; + // } + + fprintf(stderr, "Generating words...\n"); + vector<word> words = generate_words(word_sz, alph_sz); + + // for (auto w: words) { + // for (auto c: w) { + // cout << (char)(c + 'a'); + // } + // cout << "\n"; + // } + // fprintf(stderr, "Generating %d automatons...\n", my_power(alph_sz, alph_sz * states)); + // generate_automatons(states, alph_sz, words); + + Automaton aut = automaton_from_input(); + check_automaton(words, aut); +} |