Моделирование работы конечного распознавателя для последовательностей путей поиска файлов, разделенных запятой, и заканчивающихся точко

ФЕДЕРАЛЬНОЕ АГЕНТСТВО  МОРСКОГО И РЕЧНОГО ТРАНСПОРТА

Федеральное государственное образовательное  учреждение

высшего профессионального образования

«Санкт-Петербургский  государственный университет водных коммуникаций»

 

 

Кафедра ВСИ

 

 

 

Курсовая работа

По теме

«Моделирование работы конечного распознавателя для последовательностей путей поиска файлов, разделенных запятой, и заканчивающихся точкой с запятой»

Вариант 14

 

 

 

 

 

 

 

 

      

 

 

 

 

Выполнил: студент 2 курса группы ИП-21, Устинов В.В.

 

Проверила: Крупенина Н. В.

 

 

Санкт-Петербург

2012 г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретическая часть.

 

Конечный  распознаватель – это модель устройства с конечным числом состояний, которое отличает правильно образованные, или «допустимые» цепочки, от «недопустимых».

Примером задачи распознавания  может служить проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Соответствующий конечный автомат будет допускать все цепочки, содержащие нечетное число единиц, и отвергать все цепочки с четным их числом. Назовем его «контролером нечетности».

На вход конечного автомата подается цепочка символов из конечного  множества, называемого входным алфавитом автомата, и представляющего собой совокупность символов, для работы с которыми он предназначен. Как допускаемые, так и отвергаемые автоматом цепочки, состоят только из символов входного алфавита. Символы, не принадлежащие входному алфавиту, нельзя подавать на вход автомата. Входной алфавит контроллера нечетности состоит из двух символов: «0» и «1».

В каждый момент времени  конечный автомат имеет дело лишь с одним входным символом, а  информацию о предыдущих символах входной  цепочки сохраняет с помощью конечного множества состояний. Согласно этому представлению, автомат помнит о прочитанных ранее символах только то, что при их обработке он перешел в некоторое состояние, которое и является памятью автомата о прошлом.

Контролер нечетности будет  построен так, чтобы он умел запоминать, четное или нечетное число единиц ему встретилось  при чтении входной цепочки. Исходя из этого, множество состояний конструируемого автомата содержит два состояния: «чет» и «нечет».

Одно из этих состояний  должно быть выбрано в качестве начального, предполагается, что автомат начнет работу в этом состоянии. Начальным состоянием контролера нечетности будет «чет», так как на первом шаге число прочитанных единиц равно нулю, а нуль – четное число.

При чтении очередного символа  состояние автомата меняется, причем новое его состояние зависит только от входного символа и текущего состояния. Такое  изменение состояния называется переходом. При переходе может оказаться, что новое состояние совпадает со старым.

Работу автомата можно описать математически с помощью функции переходов, которая по текущему состоянию и текущему входному символу дает новое состояние автомата . Символически эта зависимость описывается так: .

Некоторые состояния  автомата выбираются в качестве допускающих, или заключительных. Если автомат, начав работу в начальном состоянии, при прочтении всей цепочки переходит в одно из допускающих состояний, то говорят, что эта цепочка допускается автоматом. Если последнее состояние автомата не является допускающим, то говорят, что автомат отвергает цепочку.

Один из удобных  способов представления конечных автоматов  – это таблица переходов. Для контролера нечетности такая таблица выглядит следующим образом:

 

	0	1
ЧЕТ	ЧЕТ	НЕЧЕТ	0
НЕЧЕТ	НЕЧЕТ	ЧЕТ	1

 

Информация  в таблице переходов размещается  в соответствии со следующими соглашениями:

• Столбцы помечены входными символами;
• Строки помечены символами состояний;
• Элементами таблицы являются символы новых состояний, соответствующих входным символам столбцов и состояниям строк;
• Первая строка помечена символом начального состояния;
• Строки, соответствующие допускающим (заключительным) состояниям, помечены справа единицами, а строки, соответствующие отвергающим состояниям, помечены справа нулями.

 

 

 

 

 

 

 

 

 

 

Практическая  часть.

 

 

1. Задача. Построить конечный детерминированный автомат для распознавания последовательностей путей поиска файлов, разделенных запятой, и заканчивающихся точкой с запятой, например (a:\data,c:\work;)
2. Составление формальной грамматики, описывающей язык, содержащий приведенную фразу.

 

R1: <предложение>::==<путь>,<предложение>; | <путь>;

R2: <путь> ::== <диск>:<папки>

R3: <папки> ::== <слово><папки> | <слово>

R4 : <диск> ::== <буква>

R5: <путь>   ::==\<слово> | \<слово>

R6: <слово>::== <симв><cлово> | <симв>

R7: <сокр> ::== <слово>.<слово>

R8: <симв> ::==<буква> | <цифра>

R9: <буква>::==a | .. | z

R10: <цифра> ::==0 | .. | 9

 

Таким образом, требуемую  грамматику можно описать следующей структурой:

• Множество терминальных символов 
  0-9, a-z, ; , /
• Множество нетерминальных символов 
  <предложение>,  < путь>, <папки>, <диск>,<путь>, <слово>, <буква>, <цифра>
• Множество правил вывода 
  R0, R1, R2, R3, R4, R5, R6, R7, R8, R9, R10

3. Построение конечного автомата

 

Для построения конечного автомата составленную грамматику путем введения дополнительных состояний надо преобразовать  к автоматному виду, в результате получится следующая таблица  переходов.

 

 

 

4. Таблица переходов

 

состояние	символ	a-z	0-9	:	/	,	;
0	начало	3	2	2	2	2	2
1	да	2	2	2	2	2	2
2	нет	2	2	2	2	2	2
3	диск	2	2	4	2	2	2
4	разд	2	2	2	5	2	2
5	разд1	6	6	2	2	2	2
6	слово	6	6	2	5	0	1

5. Граф переходов

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6. Программное моделирование работы конечного автомата

 

Файл Avto.h (Описание класса)

class Avto

{

private:

//public:

int kolsost; //Число состояний автомата

int kolsimb; //Число символов  алфавита

int ercode; //код ошибки

char *alfavit; //Входной алфавит 

int **tab; //таблица переходов

char *fin_name; //имя входго файла

struct Otchet //Отчет по каждой  строке 

{

bool det;

bool alf;

int simb;

};

public:

Otchet * otch; //множество отчетов по  строкам

int count; //кол-во входных строк  строк

char **str; //множество входных последовательностей

public:

Avto(); //конструктор задает конфигурации  автомата

void Display(); //показывает конфигурации  автомата

void DisplayTabl();

void DisplayAlf();

void Error(); //генерирует строку ошибки

bool FileName();

 

void FileName(char *fname);

void ReadFile(); //чтение входного  файла

void InAlf(); //проверяет на допустимость  строку  

int Test(); //проводит распознавание  входной строки

 

};

 

Файл Avto.cpp (реализация класса)

#include "Avto.h"

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

 

Avto::Avto()

{

ercode = 0;

FILE *f;

char *buff;

//Чтение конфигураций  автомата

f = fopen("count.conf","r");

if (!f)

{

ercode = 1;

return;

}

buff = new char [21];

fgets(buff,20,f); kolsost = atoi(buff);

fgets(buff,20,f); kolsimb = atoi(buff);

fclose(f);

 

//Чтение алфавита

f = fopen("alf.conf","r");

if (!f)

{

ercode = 1;

return;

}

alfavit = new char [kolsimb];

for (int i = 0; i<kolsimb && !feof(f); i++)

alfavit[i] = fgetc(f);

alfavit[kolsimb] = '\0';

fclose(f);

 

//Чтение таблицы переходов

f = fopen("tabl.conf","r");

if (!f)

{

ercode = 1;

return;

}

 

 

tab = new int * [kolsost];

for (i = 0; i < kolsost; i++)

tab[i] = new int [kolsimb];

i = 0;

int j = 0;

while (!feof(f) && i<kolsost)

{

fgets(buff,10,f);

tab[i][j] = atoi(buff);

j++;

if (j == kolsimb)

{

j = 0;

i++;

}

}

fclose(f);

}

 

 

void Avto::InAlf()

{

for (int num = 0; num<count; num++)

{

otch[num].simb = 0;

bool temp;

for (int i = 0; str[num][i] != '\0'; i++)

{

temp = false;

for (int j = 0; j<kolsimb; j++)

if (str[num][i] == alfavit[j])

temp = true;

if (!temp)

{

cout<<i<<endl;

otch[num].simb = i;

break;

}

}

otch[num].alf = temp;

}

}

 

void Avto::Display()

{

if (!ercode)

{

Error();

}

cout<<" Sost count: "<<kolsost<<endl;

cout<<" Simb count: "<<kolsimb<<endl;

cout<<" Alfavit: "<<alfavit<<endl;

cout<<" Table: "<<endl;

for (int i = 0; i<kolsost; i++)

{

for (int j = 0; j<kolsimb; j++)

cout<<tab[i][j]<<"  ";

cout<<endl;

}

}

 

void Avto::Error()

{

if (!ercode)

{

cout<<" No error "<<endl;

return;

}

cout<<" ERROR "<<ercode<<" -";

switch(ercode)

{

case 1: cout<<" config file not found "; break;

case 2: cout<<" incorrect input string"; break;

case 3: cout<<" string not detect "; break;

case 4: cout<<" input file not open "; break;

}

cout<<endl;

}

 

int Avto::Test()

{

for (int num = 0; num < count; num++)

{

if (!otch[num].alf)

{

otch[num].det = false;

continue;

}

int olds = 0;

int sost = 0;

for (int i = 0; str[num][i] != '\0'; i++)

{

int simb = 0;

for (int j = 0; j<kolsimb; j++)

if (str[num][i] == alfavit[j])

simb = j;

olds = sost;

sost = tab[sost][simb];

if (olds != 2 && sost == 2)

otch[num].simb = i;

}

if (sost == 1)

otch[num].det = true;

else

otch[num].det = false;

}

return 0;

}

 

void Avto::FileName(char *fname)

{

fin_name = fname;

}

 

void Avto::ReadFile()

{

FILE *fin;

fin = fopen(fin_name,"r");

if (!fin)

{

ercode = 4;

return;

}

count = 0;

 

char *buff = new char [255];

while (!feof(fin) && fgets(buff,255,fin))

count++;

fclose(fin);

 

fin = fopen(fin_name,"r");

str = new char * [count];

int i = 0;

while (!feof(fin) && i<count)

{

str[i] = new char [255];

fgets(str[i],255,fin);

for (int j = 0; str[i][j] != '\0'; j++);

str[i][j-1] = '\0';

i++;

}

fclose(fin);

otch = new Otchet [count];

}

 

bool Avto::FileName()

{

if (fin_name)

return true;

return false;

}

 

void Avto::DisplayTabl()

{

cout<<" Sost = "<<kolsost<<endl;

cout<<" Simb = "<<kolsimb<<endl;

for (int i = 0; i<kolsost; i++)

{

for (int j = 0; j<kolsimb; j++)

cout<<tab[i][j]<<" ";

cout<<endl;

}

}

 

void Avto::DisplayAlf()

{

for (int i = 0; i<kolsimb; i++)

cout<<alfavit[i]<<"  ";

cout<<endl;

}

Файл index.cpp (головная программа)

#include "Avto.h"

#include <iostream>

#include <conio.h>

#include <windows.h>

using namespace std;

 

char * Rus(const char *text)

{

char * BufRus = new char [255];

CharToOem(text, BufRus);

return BufRus;

}

 

int Menu(char **part, int num)

{

int res = 0;

char ch;

bool fl = true;

do{

system("cls");

cout<<"---------------------------------"<<endl;

cout<<Rus(" Выберите операцию ")<<endl;

for (int i=0; i<num; i++)

{

if (res == i){

cout<<"   ->  "<<part[i]<<endl;

}else{

cout<<"       "<<part[i]<<endl;

}

}

cout<<"----------------------------------"<<endl;

ch = getch();

if (int(ch)<0)

ch = getch();

if (ch == 13) fl = false;

if (int(ch) == 80 && res<num) res++;

if (int(ch) == 72 && res>=0  ) res--;

if (res == -1) res = num-1;

if (res == num) res = 0;

}while(fl);

return res;

}

 

 

 

int MenuMain()

{

int count = 3;

char ** list =  new char * [count];

list[0] = new char [] = Rus("Провести распознавание");

list[1] = new char [] = Rus("Конфигурации  автомата");

list[2] = new char [] = Rus("Выход");

return Menu(list,count);

}

 

int MenuConfig()

{

int count = 4;

char ** list = new char * [count];

list[0] = new char [] = Rus("Входной файл");

list[1] = new char [] = Rus("Показать таблицу переходов");

list[2] = new char [] = Rus("Показать входной алфавит");

list[3] = new char [] = Rus("В главное  меню");

return Menu(list,count);

}

 

void Run(Avto * obj)

{

if (!obj->FileName())

{

cout<<Rus("Не задан входной файл")<<endl;