Построение и анализ КДА. ДИПЛОМНАЯ РАБОТА

};

class Cell{ public:

Cell(): s(0), y(0) {}

Cell(State ns, Output ny): s(ns), y(ny) {} Cell(const Cell& cs): s(cs.s), y(cs.y) {}

State s; Output y;

};

typedef std::map<Input,Cell> Cells; typedef std::map<State,Cells> Table; typedef std::pair<State,Cells> Line;

class TableAutomate: public virtual AbstractAutomate{ public:

TableAutomate(): T(), X(), Y(){}

TableAutomate( const Table& nT, const Inputs& nX, const Outputs& nY): T(nT), X(nX), Y(nY){}

TableAutomate(const TableAutomate& A): T(A.T), X(A.X), Y(A.Y) {}

State& Delta(const State& s, const Input& x) { return T[s][x].s; } Output& Lambda(const State& s, const Input& x) { return T[s][x].y; }

AutomateType Type() { return AutomateType(T.size(), X.size(), Y.size()); }

Table::iterator AddState(const Line& l);

friend std::ostream& operator<<(std::ostream&, TableAutomate&);

protected: Inputs X; Outputs Y; Table T;

void InitStates(const States&);

};

class TableAutonomousAutomate: public virtual AbstractAutonomousAutomate{ public:

};

#endif /* _AUTOMATE_H */

//

//C++ Implementation: Automate

//Description: This program generate by order n Fibonacci numbers

//from first to n-th

//

//Author: Sin <sin@altlinux.ru>, (C) 2004

//Copyright: See COPYING file that comes with this distribution

#include <automate.h> #include <exception.h> #include <iostream>

30

#include <set> #include <map>

std::ostream& operator<<(std::ostream& os, TableAutomate& A){ int i = A.X.size();

while(i--)

os << "---"; os << "----\n"; os << "\\ d|\n"; os << " \\ |";

for(Inputs::iterator x = A.X.begin(); x != A.X.end(); x++) os <<" "<<*x;

os << "\nl \\|\n"; i = A.X.size(); while(i--)

os << "---"; os << "----\n";

for(Table::iterator s = A.T.begin(); s != A.T.end(); s++){ os << " |";

for(Inputs::iterator x = A.X.begin(); x != A.X.end(); x++)

for(Inputs::iterator x = A.X.begin(); x != A.X.end(); x++) os << (s->second)[*x].y << " \\";

os << '\n';

for(i = 0; i < A.X.size(); i++) os << "---";

os << "----" << std::endl;

}

os << std::endl; return os;

}

Table::iterator TableAutomate::AddState(const Line& l) { std::pair<Table::iterator,bool> p = T.insert(l); if(!p.second)

throw EAutomate(BAD_VALUE); return p.first;

}

void TableAutomate::InitStates(const States& S) { States::iterator p = S.begin();

Cells cs;

while(p != S.end()) T.insert(Line(*p++,cs));

}

#ifndef FREPRESENT_H #define FREPRESENT_H

//

// C++ Interface: frepresent

//

31

//Description:

//Author: Sin <sin@altlinux.ru>, (C) 2004

//Copyright: See COPYING file that comes with this distribution

#include <vector> #include <fstream> #include <string> #include <map>

typedef std::map<std::string, std::string> StringFunction; typedef std::pair<std::string, std::string> StringFunctionLine;

class LogFunction: public StringFunction{ private:

int dimx, dimy; std::istream& rule;

bool FetchNext();

public:

void PrintFunc();

LogFunction(const int, const int, std::istream&);

void BuildOnPrefix(int);

int BuildOnPrefixIgnoreDim(int); int BuildOnOppos(int, bool);

int RunOnPrefix(int);

};

#endif

//

//C++ Implementation: fprepresent

//Description:

//Параметры: размерность отображения: X^sizex->Y^sizey и поток,

//определяющий закон функционирования

//

//Author: Sergey Putyatinsky, Sin <sin@altlinux.ru>, (C) 2004

//Copyright: See COPYING file that comes with this distribution

#include <frepresent.h> #include <exception.h> #include <iostream>

LogFunction::LogFunction(const int sizex, const int sizey, std::istream &rule_f): StringFunction(), dimx(sizex), dimy(sizey), rule(rule_f), sequence() {}

bool LogFunction::FetchNext(){

32

static std::string x, y; unsigned char ch;

if(size()){

x.erase(x.begin());

x+=y[0];

y.erase(y.begin());

rule>>ch;

y+=ch;

StringFunctionLine p(x, y);

std::pair<StringFunction::iterator, bool> inserted=insert(p);

bool result = inserted.second; if(!result){

StringFunction::iterator ln=find(x); if(ln->second==y){

//std::cerr<<'!'<<x<<'!'<<std::endl; result = true;

}

}

if(result) sequence+=ch; return result;

}

else{

x.erase(x.begin(), x.end()); y.erase(y.begin(), y.end()); for(int i=0; i<dimx; i++){

rule>>ch;

x+=ch;

}

for(int i=0; i<dimy; i++){ rule>>ch;

y+=ch;

}

sequence += x; sequence += y;

StringFunctionLine p(x, y); insert(p);

return true;

}

}

void LogFunction::BuildOnPrefix(int pref){ clear();

for(int i=0; i<pref; i++) if(!FetchNext()){ clear();

throw EPrefix();//EPrefix;//exception in case of contradiction

}

33

}

int LogFunction::BuildOnOppos(bool rebuild, int offset){ int i=0;

if(rebuild) clear();

if(offset >= 0) rule.seekg(offset); while(FetchNext() && rule)

i++; return i;

}

void LogFunction::PrintFunc(){ StringFunction::const_iterator i;

for(i=begin(); i!=end(); ++i){ std::cout<<i->first<<'\t'<<i->second<<std::endl;

}

}

void LogFunction::PrintSequence(){ std::cout<<sequence<<std::endl;

}

int LogFunction::RunOnPrefix(){ int i=0; StringFunction::iterator it; std::string x, y;

unsigned char ch;

for(i=0; i<dimx; i++){ rule>>ch;

x+=ch;

}

for(i=0; i<dimy; i++){ rule>>ch;

y+=ch;

}

it=find(x); int j=0;

for(; !rule.eof(); j++){ if((it!=end())&&((*this)[x]==y)){

x.erase(x.begin());

x+=y[0];

y.erase(y.begin());

rule>>ch;

y+=ch;

it=find(x);

}

else return j;

}

return j;

}

34

int LogFunction::BuildOnPrefixIgnoreDim(int pref){ dimx=0;

int i=0; //pref-dimy-dimx+1

//по оставшейся части префикса. while(i<pref-dimy-dimx+1){

dimx++;

clear();

i=0;

for(int j=0; j<pref-dimy-dimx+1; j++){ if(FetchNext()) i++;

else break;

}

}

return dimx;

}

//

//C++ Implementation: fautomate

//Description: f-represent automate

//Author: Sin <sin@altlinux.ru>, (C) 2004

//Copyright: See COPYING file that comes with this distribution

#include <frepresent.h>

FAutomate::FAutomate(LogFunction& func): TableAutomate(), length(0){ State s = 0;

Output y = 0; std::string::size_type len;

for(LogFunction::const_iterator i = func.begin(); i != func.end(); s++, i++){ std::pair<StringState::const_iterator, bool> p =

stringstate.insert(StringStateLine(i->first+i->second,s)); if(p.second)

if((len = (p.first)->first.size()) > length) length = len;

if(stringoutput.insert(StringOutputLine(i->second, y)).second) Y.insert(y++);

}

BuildTable(func.GetSequence());

}

FAutomate::FAutomate(const int len, std::istream& is): TableAutomate(), length(len){ std::string x, seq, y;

unsigned char ch; State s = 0; Output out = 0;

for(int i=0; i<len; i++){ is>>ch;

35

x+=ch;

seq+=ch;

}

while(is && !is.eof()){ if(!stringstate.insert(std::pair<std::string,State>(x, s++)).second)

break;

x.erase(x.begin());

is>>ch;

x+=ch;

seq+=ch;

y.clear();

y+=ch;

if(stringoutput.insert(StringOutputLine(y, out)).second) Y.insert(out++);

}

BuildTable(seq);

}

void FAutomate::BuildTable(const std::string& sequence){ T.clear();

X.clear(); X *= 1;

Cells cs; std::string::size_type i, len;

State s = stringstate[sequence.substr(0, length)];

//std::cerr<<"seq 0: "<<sequence.substr(0, length) << "state: " << s << std::endl; for(i = 1, len = (sequence.size() - length + 1); i < len; i++){

State ns = stringstate[sequence.substr(i, length)];

//std::cerr<<"seq "<<i<< ": "<<sequence.substr(i, length) << "state: " << ns << st cs[0] = Cell(ns, stringoutput[sequence.substr(i,1)]);

T.insert(Line(s, cs)); s = ns;

}

}

//

//C++ Implementation: logfunction

//Description:

//Программа запрашивает входной файл с иррациональной

//последовательностью через стандартный поток ввода, а длину

//слова для f-представления через параметр коммандной строки

//На выходе - длина f-представимого начального отрезка, определяемое

//последовательностью, а также функчия f-представления.

//

//Author: Sin <sin@altlinux.ru>, (C) 2004

//Copyright: See COPYING file that comes with this distribution

#include <cstdlib> #include <string> #include <sstream>

36

#include <iostream> #include <fstream> #include <vector> #include <map> #include <getopt.h>

#include <frepresent.h>

#define MAXNUMBER 10000

int isvalidentry(std::string sx, unsigned char sy);

char* program_name;

void read_options(int, char*[]);

std::vector<std::string> x; std::string y;

read_options(argc, argv);

std::stringstream *buf; if(build_bit){

buf = new std::stringstream;

for(int i = 0; i < length+number*increment; i++) buf->put(std::cin.get());

}

while(number--){ LogFunction* func; int len; if(build_bit){

int dim = dimension < (length-1) ? dimension : (length-1); buf->seekg(0,std::ios::beg);

do{

try {

func = new LogFunction(dim, 1, *buf); func->BuildOnPrefix(length-dim); break;

}

catch(EPrefix){

37

buf->seekg(0,std::ios::beg); delete(func);

}

} while (dim++ < length); len = length - dim; dimension = dim;

}

else{

func = new LogFunction(dimension, 1, std::cin); len=func->BuildOnOppos(true, offset);

length = dimension + len;

}

if(seq_bit) func->PrintSequence();

if(info_bit)

std::cout<<"start="<< (offset < 0 ? 0 : offset) <<" length="<<len << " sequence="<<length << " size="<<func->size()<<"dimension=" <<dimension<<std::endl;

if(func_bit) func->PrintFunc();

if(auto_bit){

FAutomate A(*func); AutomateType t = A.Type(); std::cout<<t; std::cout<<A;

}

delete func;

if(build_bit){

length += increment;

}

else{

dimension += increment; if(offset < 0)

offset = len + 1;

else

exit(exit_code);

38

}

void read_options(int argc, char* argv[]){ int next_option;

const char* const short_options = "hfsail:d:n:u:o:"; const option long_options[] = {

{"help", 0, 0, 'h'}, {"function", 0, 0, 'f'}, {"sequence", 0, 0, 's'}, {"automate", 0, 0, 'a'}, {"info", 0, 0, 'i'}, {"length", 1, 0, 'l'}, {"dimension", 1, 0, 'd'}, {"number", 1, 0, 'n'}, {"increment", 1, 0, 'u'}, {"offset", 1, 0, 'o'}

};

do{

next_option = getopt_long (argc, argv, short_options, long_options, 0); switch(next_option){

case 'h': print_usage(std::cout, 0);

case 'f':

func_bit = func_bit ? false : true; break;

case 'i':

info_bit = info_bit ? false : true; break;

case 's':

seq_bit = seq_bit ? false : true; break;

case 'a':

auto_bit = auto_bit ? false : true; break;

case 'u':

increment = atoi(optarg); break;

case 'n':

number = atoi(optarg); break;

case 'd':

dimension = atoi(optarg); build_bit = false; break;

case 'l':

length = atoi(optarg); build_bit = true; break;

case 'o':

offset = atoi(optarg); break;

case '?': print_usage(std::cerr, 1);

case -1:

39