понедельник, 17 января 2011 г.

Распознавание строк конечным автоматом

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

Конечный автомат (КА) – это простейший распознаватель без вспомогательной памяти. Его входная головка читает символы входной ленты и перемещается на одну ячейку вправо на каждом шаге работы автомата. КА имеет конечное множество управляющих состояний, среди которых выделены начальное состояние и заключительные состояния.

КА создается для конкретного регулярного языка. Закончив просмотр входной строки, КА должен выдать заключение о том, принадлежит или не принадлежит эта строка соответствующему языку. КА является эффективным способом определения регулярных языков.
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

int main(int argc, char *argv[])
{
fstream read;//поток для чтения из файла
read.open("avtomat.txt",ios::in);//открываем файл avtomat.txt
if(!read){cout<<"File read Error!"<<endl;system("PAUSE");return EXIT_SUCCESS;};//если возникла ошибка при чтении
char start,end[128],stroka[128],q; //start - начальное состояние, end - конечные состояния, stroka - строка для распознавания
int razmer; //razmer - количество правил
read>>start;read.get();cout<<"Start "<<start<<endl; //считали начальное состояние
read.getline(end,128,'\n');cout<<"Finish "<<end<<endl;//считали конечные состояния
read>>razmer;read.get(); //считали количество правил
char pravila[3][razmer],temp[4];//pravila массив с правилами, temp промежуточный массив для чтения правил
for(int i=0;i<razmer;i++)//считываем правила
{
read.getline(temp,4,'\n');cout<<temp<<endl;
for(int j=0;j<3;j++)
pravila[j][i]=temp[j];

};
cout<<endl<<"Vvedite stroky ";cin.getline(stroka,128,'\n');//считываем строку для распознавания
q=start;//задаём начальные условия работы автомата
for(int i=0;i<strlen(stroka);i++)//сам автомат
{
for(int j=0;j<razmer;j++)
{
if (stroka[i]==pravila[1][j]&&q==pravila[0][j])
{                                                             
q=pravila[2][j];
break;
};
}; 
cout<<q<<endl; //Выводим текущее состояние          
};
for(int i=0;i<strlen(end);i++)
{
if(q==end[i])
{
cout<<endl<<"Raspoznano :)"<<endl;//если последнее состояние заключительное то строка распознана
system("PAUSE");return EXIT_SUCCESS;
};
};
cout<<endl<<"Ne raspoznano :("<<endl;//в противном случае строка не распознана
system("PAUSE");return EXIT_SUCCESS;
}


Программа скомпилирована в Dev-C++ 4.9.9.2 (В Microsoft Visual Studio возможны ошибки)

Up для работы в Microsoft Visual Studio С++ необходимо в программе строчку
char pravila[3][razmer],temp[4];
заменить на
char **pravila = new char*[3];
for(int i=0;i<3;i++) pravila[i]=new char[razmer];
char temp[4];

2 коммент.:

Unknown комментирует...

правила в файле в каком виде должны быть?

GeaR комментирует...

В следующем виде:

A
C
6
A0B
B0A
C0B
A1A
B1C
C1B

Привет Константину Александровичу ;)

Отправить комментарий