Способы представления функции переходов

 

Командный способ. Каждую команду КА записывают в форме , где .

Табличный способ. Строки таблицы переходов соответствуют входным символам автомата t Î T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции . Неопределенным значениям функции переходов соответствуют пустые ячейки таблицы.

Графический способ. Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автомата. Дуга ведет из состояния в состояниe и помечается списком всех символов t Î T, для которых . Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими окружностями.

4 Структурная организация данных

Основная часть данных хранится и обрабатывается в двух классах Grammar (грамматика) и FAutomat (конечный автомат), представленных в таблице 4.1.

 

Таблица 4.1 – Описание полей классов

 

Поле	Тип	Назначение
Класс Grammar
N	charset	множество нетерминалов грамматики
T	charset	множество терминалов грамматики
P	rulemap	множество правил грамматики
S	char	начальный символ грамматики
Класс FAutomat
*G	Grammar	связанная с данным автоматом грамматика
Q	charset	множество состояний автомата
T	charset	множество входных символов автомата
F	ftable	таблица правил автомата
H	char	начальное состояние автомата
Z	charset	множество конечных состояний автомата
MustPaint	int	флаг отрисовки графа

 

Для хранения таблицы правил конечного автомата используется структура:

struct posit{

long x, y;

long double a;

};

 

Для создания отображения используется класс компаратора:

 

struct rulecmp{

bool operator()(const char c1, const char c2){

return (c1 < c2);

}

};

5 Спецификации основных процедур и функций программного средства

 

Основные функции программного средства описаны в виде методов классов Grammar и Fautomat в таблице 5.1.

 

Таблица 5.1 – Спецификации основных функций

 

Название	Входные параметры	Выходные параметры	Назначение
Методы класса Grammar
int IsRegular()	Нет	Возвращает 1, если грамматика регулярная и 0 в противном случае	Проверка грамматики на принадлежность к классу регулярных грамматик
void InGrammar(char *fname)	Имя файла	Нет	Ввод грамматики из текстового файла
string AsString()	Строка, содержащая грамматику	Нет	Возвращает грамматику в виде строки
void OutGrammar(char *fname)	Имя файла	Нет	Вывод грамматики в текстовый файл
Методы класса FAutomat
void SetGrammar(Grammar *NG)	Указатель на связанную грамматику	Нет	Связывает грамматику с данным конечным автоматом

 

6 Алгоритм решения задачи

 

Укрупненная схема алгоритма программного средства представлена на рисунке 6.1.

 

Приложение Б

(обязательное)

Пример оформления приложений отчета лабораторной работы

 

Приложение А

(обязательное)

Контрольный пример

Исходная регулярная грамматика и соответствующий ей недетерминированный конечный автомат представлены на рисунке А.1.

 

 

 

Р

 

Рисунок А.1 – Исходная КС-грамматика и НКА

Результирующий детерминированный конечный автомат, построенный по заданному недетерминированному конечному автомату, представлен на рисунке А.2.

 

 

Рисунок А.2 – Результирующий ДКА

Приложение Б

(обязательное)

Текст программы

 

Unit2.h

 

#include <fstream.h>

#include <math.h>

#include <sysutils.hpp>

#include <graphics.hpp>

#include <grids.hpp>

#include <map>

#include <set>

#include <string>

#include <list>

#include <vector>

 

using std::string;

using std::map;

using std::multimap;

using std::set;

using std::pair;

 

// компаратор для работы в отображениях

struct rulecmp{

bool operator()(const char c1, const char c2){

return (c1 < c2);

}

};

 

typedef string rule_r;

typedef char rule_l;

typedef pair<rule_l, rule_r> rule;

typedef multimap<rule_l, rule_r, rulecmp> rulemap;

typedef set<char> charset;

 

// класс грамматики

class Grammar{

public:

charset N; // мн-во нетерминалов

charset T; // множество терминалов

rulemap P; // множество правил

char S; // начальный символ

int IsRegular(); // проверка грамматики на регулярность

void InGrammar(char *fname); // ввод грамматики из файла

string AsString(); // вывод грамматики в строку

void OutGrammar(char *fname); // вывод грамматики в файл

};

 

typedef map<char, map<char, charset> > ftable;

 

// класс конечного автомата

class FAutomat{

public:

Grammar *G; // связанная грамматика

charset Q; // множество состояний

charset T; // множество входных символов

ftable F; // таблица правил

char H; // начальное состояние

charset Z; // множество конечных состояний

int MustPaint; // флаг отрисовки графа

FAutomat(){

MustPaint = 0;

}

void SetGrammar(Grammar *NG); // связывание с грамматикой

void CreateAutomat(); // создание автомата из грамматики

void PaintAutomat(TCanvas * Canvas, long w, long h); // отрисовка графа

void OutToTable(TStringGrid * Grid); // вывод таблицы правил в StringGrid

void CreateDeterm(); // преобразование в ДКА

};

 

Unit2.cpp

 

#include "Unit2.h"

 

int Grammar::IsRegular(){

if (N.empty() || P.empty())

return 0;

for(rulemap::iterator i = P.begin(); i!= P.end(); i++){

if (!N.count(i->first))

return 0;

//по длине правой части

switch(i->second.length()){

case 1:{

if (!T.count(i->second[0]))

return 0;

break;

}

case 2:{

if (!T.count(i->second[0]) ||!N.count(i->second[1]))

return 0;

break;

}

default:

return 0;

}

}

return 1;

}

 

void Grammar::InGrammar(char *fname){

long n, i;

rule r;

char c;

 

ifstream fi(fname);

N.clear();

T.clear();

P.clear();

// ввод нетерминалов

fi >> n;

for (i = 0; i < n; i++){

fi >> c;

N.insert(c);

}

// ввод терминалов

fi >> n;

for (i = 0; i < n; i++){

fi >> c;

T.insert(c);

}

// ввод правил

fi >> n;

for (i = 0; i < n; i++){

fi >> r.first >> r.second;

P.insert(r);

}

// начальный символ

fi >> S;

}

 

string Grammar::AsString(){

string res = "";

charset::iterator i;

res += "Nonterminals (";

res += IntToStr(N.size()).c_str();

res += "): ";

for (i = N.begin(); i!= N.end(); i++){

res += *i;

res += " ";

}

res += "\nTerminals (";

res += IntToStr(T.size()).c_str();

res += "): ";

for (i = T.begin(); i!= T.end(); i++){

res += *i;

res += " ";

}

res += "\nRules (";

res += IntToStr(P.size()).c_str();

res += ")\n";

for (rulemap::iterator j = P.begin(); j!= P.end(); j++){

res += "\t";

res += j->first;

res += " -> " + j->second + "\n";

}

 

res += "Starting symbol: ";

res += S;

res += "\n";

return res;

}

 

void Grammar::OutGrammar(char *fname){

ofstream fo(fname);

charset::iterator i;

fo << N.size() << "\n";

for (i = N.begin(); i!= N.end(); i++)

fo << *i;

fo << "\n" << T.size() << "\n";

for (i = T.begin(); i!= T.end(); i++)

fo << *i;

fo << "\n" << P.size() << "\n";

for (rulemap::iterator j = P.begin(); j!= P.end(); j++)

fo << j->first << " " << j->second << "\n";

fo << "\n" << S;

}

 

void FAutomat::SetGrammar(Grammar *NG){

G = NG;

}

 

void FAutomat::CreateAutomat(){

rulemap::iterator i, j;

rule r;

char c, t;

int k;

// поиск незанятого символа

for(c = 'A'; G->N.count(c); c++);

// поиск правил вида A -> a без A -> aB

for(i = G->P.begin(); i!= G->P.end(); i++)

if (i->second.length() == 1 && G->T.count(i->second[0])){

for(j = G->P.lower_bound(i->first), k = G->P.count(i->first); k; j++, k--)

if (j->second.length() == 2 && j->second[0] == i->second[0] && G->N.count(j->second[1]))

break;

if (!k){

// добавление правила вида A -> aC

r.first = i->first;

r.second = i->second + c;

G->P.insert(r);

G->N.insert(c);

}

}

// начальный символ

H = G->S;

// состояния

Q = G->N;