Конечный автомат (КА) – это простейший распознаватель без вспомогательной памяти. Его входная головка читает символы входной ленты и перемещается на одну ячейку вправо на каждом шаге работы автомата. КА имеет конечное множество управляющих состояний, среди которых выделены начальное состояние и заключительные состояния.
КА создается для конкретного регулярного языка. Закончив просмотр входной строки, КА должен выдать заключение о том, принадлежит или не принадлежит эта строка соответствующему языку. КА является эффективным способом определения регулярных языков.
#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 коммент.:
правила в файле в каком виде должны быть?
В следующем виде:
A
C
6
A0B
B0A
C0B
A1A
B1C
C1B
Привет Константину Александровичу ;)
Отправить комментарий