Моделирование работы конечного распознавателя

Размещено на http://www.allbest.ru

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

Моделирование работы конечного распознавателя

Учебная цель. Получение практических навыков построения моделей конечных распознавателей.

Теоретические сведения.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q0, F), где

Q - конечное множество состояний;

T - конечное множество допустимых входных символов (входной алфавит);

D - функция переходов (отображающая множество Q?(T{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;

q0 Q - начальное состояние управляющего устройства;

F Q - множество заключительных состояний.

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

Рис. 9.2:

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

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара (q, w) Q?T*, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q0, w) называется начальной, а конфигурация (q, e), где q F - заключительной (или допускающей).

Пусть M = (Q, T, D, q0, F) - НКА. Тактом автомата M называется бинарное отношение , определенное на конфигурациях M следующим образом: если p D(q, a), где a T {e}, то (q, aw) (p, w) для всех w T*.

Будем обозначать символом + (*) транзитивное (рефлексивно- транзитивное) замыкание отношения .

Говорят, что автомат M допускает цепочку w, если (q0, w) *(q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е.

Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.

Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия:

D(q, e) = для любого q Q, и

D(q, a) содержит не более одного элемента для любых q Q и a T.

Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) = p вместо D(q, a) = {p}.

Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символом a T {e}, соединяет две вершины p и q, если p D(q, a). На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром).

Пример 9.1. Пусть L = L(r), где r = (a|b)*a(a|b)(a|b).

Недетерминированный конечный автомат M, допускающий язык L:

	M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},

где функция переходов D определяется так:

	D(1, a) = {1, 2},	D(3, a) = {4},
	D(2, a) = {3},	D(3, b) = {4},
	D(2, b) = {3}.

Диаграмма автомата приведена на рис. 9.2, а.

Детерминированный конечный автомат M, допускающий язык L:

	M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},

где функция переходов D определяется так:

	D(1, a) = 2,	D(5, a) = 8,
	D(1, b) = 1,	D(5, b) = 6,1000
	D(2, a) = 4,	D(6, a) = 2,
	D(2, b) = 7,	D(6, b) = 1,
	D(3, a) = 3,	D(7, a) = 8,
	D(3, b) = 5,	D(7, b) = 6,
	D(4, a) = 3,	D(8, a) = 4,
	D(4, b) = 5,	D(8, b) = 7.

Диаграмма автомата приведена на рис. 9.2, б.

Рис. 9.3:

Пример 9.2. Диаграмма ДКА, допускающего множество чисел в десятичной записи, приведена на рис. 9.4.

Рис. 9.4:

Пример 9.3. Анализ цепочек.

При анализе цепочки w = ababa автомат из примера 9.2, а, может сделать следующую последовательность тактов:

(1, ababa) (1, baba) (1, aba) (2, ba) (3, a) (4, e).

Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом.

При анализе цепочки w = ababab автомат из примера 9.2, б, должен сделать следующую последовательность тактов:

(1, ababab) (2, babab) (7, abab) (8, bab) (7, ab) (8, b) (7, e).

Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.

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

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

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

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

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

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

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

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

Учитывая, что состояния «чет» и «нечет» означают соответственно, четное и нечетное количество прочитанных единиц, определим функцию переходов контролера нечетности следующим образом:

Эта функция переходов отражает тот факт, что четность меняется тогда и только тогда, когда на входе читается единица.

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

Переход автомата из состояния в состояние при чтении входного символа Х будем наглядно изображать так: . Например, для контролера нечетности можно написать: . Аналогичным образом можно изобразить последовательность переходов:

Эта запись показывает, как автомат в состоянии «ЧЕТ» применяется к цепочке «1101». Входную цепочку «101» автомат отвергает, т.к. она переводит его из начального состояния в состояние, не являющееся допускающим. Символически это изображается так: .

Контролер нечетности распознает множество цепочек, состоящих из нулей и единиц, и содержащее нечетное число единиц. Множество всех цепочек, распознаваемых конечным автоматом, называется регулярным множеством.

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



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

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

Столбцы помечены входными символами;

Строки помечены символами состояний;

Элементами таблицы являются символы новых состояний, соответствующих входным символам столбцов и состояниям строк;

Первая строка помечена символом начального состояния;

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

Таким образом, приведенная таблица переходов задает конечный автомат, у которого:

Входное множество ={0,1};

Множество состояний ={ЧЕТ, НЕЧЕТ};

Функции переходов:

Начальное состояние = {ЧЕТ};

Допускающие состояния = {НЕЧЕТ}.

Простейшая программная реализация КА - контроллера нечетности:

#include "stdafx.h"

#include "iostream.h"

#include "stdio.h"

#include "conio.h"

int per (int tsost, char tsymb)

{int slsost;

switch (tsymb)

{ case '0': if (tsost==0) slsost=0; else slsost=1;

case '1': if (tsost==1) slsost=0; else slsost=1;}

return slsost;

};

int main()

{ int i,kol,tsost,slsost;

char ch, inpstr[80] ;

printf("ENTER STRING ");

i=0;

while ((ch=getch()) !=13 && i<80) //пока не нажата клавиша <Enter>

{putch(ch);

inpstr[i++]=ch;}

inpstr[i]='\0';

kol=i-1;

printf("\n input string:");

printf(inpstr);

tsost=0;

for (i=0;i<=kol;i=i+1)

{

slsost=per(tsost,inpstr[i]);

tsost=slsost;

};

switch (slsost)

{ case 0:cout<<"\n STRING is WRONG ";

case 1:cout<<"\n STRING is RIGHT ";};

return 0;

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

Задания на Курсовую работу

Построить детерминированный конечный распознаватель для:

последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных запятыми, и заканчивающейся символом #, например, (+65.372,-785.34,457.7#);

последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных точкой с запятой, и заканчивающейся символом #, например, (+65.372;-785.34;457.7#);

последовательности действительных чисел в формате с фиксированной точкой (число не может начинаться и заканчиваться десятичной точкой), разделенных слэшами, и заканчивающейся символом #, например, (+65.372/-785.34/457.7#);

последовательности действительных чисел в формате с плавающей точкой, разделенных запятой, и заканчивающейся символом #, например, (65.3Е-2,+785.3E4,457.7E+2#);

последовательности действительных чисел в формате с плавающей точкой, разделенных точкой с запятой, и заканчивающейся символом #, например, (65.3Е-2;+785.3E4;457.7E+2#);

последовательности действительных чисел в формате с плавающей точкой, разделенных слэшами, и заканчивающейся символом #, например, (65.3Е-2/+785.3E4/457.7E+2#);

последовательности целых чисел, разделенных запятыми, и заканчивающейся символом #, например, (65,+78534,-4577#);

последовательности целых чисел, разделенных точкой с запятой, и заканчивающейся символом #, например, (65;+78534;-4577#);

последовательности целых чисел, разделенных слэшами, и заканчивающейся символом #, например, (65/+78534/-4577#);

последовательности составных имен объектов, разделенных слэшами, и заканчивающейся символом # , т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w/e.w1/re.r5.а#);

последовательности составных имен объектов, разделенных точкой с запятой, и заканчивающейся символом # , т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w;e.w1;re.r5.а#);

последовательности составных имен объектов, разделенных запятыми, и заканчивающейся символом # - т.е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w,e.w1,re.а,r5#);

полной и сокращенной спецификации файла, например (a:\w1\data.pas) либо (ааа.dat);

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

последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01.12.2001},{05.07.2003});

последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01.12.2001};{05.07.2003});

последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01.12.01},{05.07.03});

последовательности элементов типа «дата» в немецком формате (ДД.ММ.ГГ),, разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01.12.01},{05.07.03});

последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01/12/2001},{05/07/2003});

последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, например, ({01/12/2001};{05/07/2003});

последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГ), разделенных запятыми, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01/12/01},{05/07/03});

последовательности элементов типа «дата» в американском формате (ММ/ДД/ГГ), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться двумя символами, например, ({01/12/01};{05/07/03}).

Пример выполнения курсовой работы

Построить детерминированный конечный распознаватель для последовательности элементов типа «дата» в формате, удобном для сортировки (ГГГГ/ММ/ДД), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, последовательность должна завершаться знаком «#», например, ({2001/12/01};{2005/07/03}#).

Выполнение курсовой работы распадается на следующие этапы:

Составление формальной грамматики, описывающей язык, содержащий приведенную фразу;

Построение конечного автомата по созданной грамматике;

Составление блок-схемы и программы, моделирующей работу конечного автомата.

Составление формальной грамматики.

Фраза языка представляет собой список, поэтому из начального символа грамматики должен выводится список:

R0: <предложение>::==<фраза>#

R1: <фраза>::==<фраза>;<дата> | <дата>

Дата представляет собой линейную структуру:

R2: <дата>::=={<год>/<месяц>}

Аналогично год, месяц и день:

R3: <год>::==<цифра><цифра><цифра><цифра>

R4: <месяц>::==<месяцб>/<деньб>|<месяцм>/<деньм>|<февраль>/<деньф>

R5: <месяцб>::=01|03|05|07|08|10|12

R6: <месяцм>::=04|06|09|11

R7: <февраль>::=02

R8: <деньб>::==<цифра2><цифра>| 3<цифра1>

R9: <деньм>::==<цифра2><цифра>| 30

R10: <деньф>::==<цифра1><цифра>| 2<цифра3>

R11: <цифра>::==0|1|2|3|4|5|6|7|8|9|

R12: <цифра1>::==0|1

R13: <цифра2>::==0|1|2

R14: <цифра3>::==0|1|2|3|4|5|6|7|8

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

Множество терминальных символов: {,},/,0,1,2,3,4,5,6,7,8,9.

Множество нетерминальных символов: <фраза>, <дата>, <год>, <месяц>, <день>, <цифра>, <цифра1>, <цифра2>.

Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14. конечный автомат число программа

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

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

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

0

1

2

3

4

5

6

7

8

9

{

}

/

;

#

да

нет

дата

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

год

нет

нет

нет

нет

год

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

Цг1

нет

нет

нет

нет

нет

Цг1

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

Цг2

нет

нет

нет

нет

нет

Цг2

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

Цг3

нет

нет

нет

нет

нет

Цг3

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

Цг4

нет

нет

нет

нет

нет

Цг4

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

мес

нет

нет

мес

Мес0

Мес1

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Мес0

нет

месб

фев

месб

месм

месб

месм

месб

месб

месм

нет

нет

нет

нет

нет

Мес1

месб

месм

месб

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

месб

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денб

нет

нет

месм

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денм

нет

нет

фев

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денф

нет

нет

денб

Дб1

Дб1

Дб1

Цф1

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Дб1

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

нет

нет

нет

нет

нет

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

разд

нет

нет

нет

Цф1

Дб2

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

денм

Дб1

Дб1

Дб1

Цф0

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Цф0

Дб2

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

разд

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

дата

да

денф

Дб1

Дб1

Цф3

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

нет

Цф3

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

Дб2

нет

нет

нет

нет

нет

нет

нет

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

#include "stdafx.h"

#include "iostream.h"

#include "stdio.h"

#include "conio.h"

int main()

{ int i,j,kol,tsost,slsost,tsymb;

int tabl[23][15]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net

{1,1,1,1,1,1,1,1,1,1,3,1,1,1,1},//data

{4,4,4,4,4,4,4,4,4,4,1,1,1,1,1},//god

{5,5,5,5,5,5,5,5,5,5,1,1,1,1,1},//cg1

{6,6,6,6,6,6,6,6,6,6,1,1,1,1,1},//cg2

{7,7,7,7,7,7,7,7,7,7,1,1,1,1,1},//cg3

{1,1,1,1,1,1,1,1,1,1,1,1,8,1,1},//cg4

{9,10,1,1,1,1,1,1,1,1,1,1,1,1,1},//mes

{1,11,13,11,12,11,12,11,12,11,1,1,1,1,1},//mes0

{11,12,11,1,1,1,1,1,1,1,1,1,1,1,1},//mes1

{1,1,1,1,1,1,1,1,1,1,1,1,14,1,1},//mesb

{1,1,1,1,1,1,1,1,1,1,1,1,18,1,1},//mesm

{1,1,1,1,1,1,1,1,1,1,1,1,21,1,1},//feb

{15,15,15,17,1,1,1,1,1,1,1,1,1,1,1},//denb

{16,16,16,16,16,16,16,16,16,16,1,1,1,1,1},//db1

{1,1,1,1,1,1,1,1,1,1,1,20,1,1,1},//db2

{16,16,1,1,1,1,1,1,1,1,1,1,1,1,1},//cf1

{15,15,15,19,1,1,1,1,1,1,1,1,1,1,1},//denm

{16,1,1,1,1,1,1,1,1,1,1,1,1,1,1},//cf0

{1,1,1,1,1,1,1,1,1,1,1,1,1,2,0},//razd

{15,15,22,1,1,1,1,1,1,1,1,1,1,1,1},//denf

{16,16,16,16,16,16,16,16,1,1,1,1,1,1,1}//cf3

};

printf("matrica\n");

for (i=0;i<23;i++) {for (j=0;j<15;j++) printf("%4d",tabl[i][j]); printf("\n");};

char ch, inpstr[80] ;

printf("\n ENTER STRING ");

i=0;

while ((ch=getch()) !=13 && i<80)

{putch(ch);

inpstr[i++]=ch;}

inpstr[i]='\0';

kol=i-1;

printf("\n input string:");

printf(inpstr);

printf("\n");

tsost=2;

for (i=0;i<=kol;i=i+1)

{ tsymb=inpstr[i];

switch (tsymb)

{ case '0': slsost=tabl[tsost][0]; break;

case '1': slsost=tabl[tsost][1]; break;

case '2': slsost=tabl[tsost][2]; break;

case '3': slsost=tabl[tsost][3]; break;

case '4': slsost=tabl[tsost][4]; break;

case '5': slsost=tabl[tsost][5]; break;

case '6': slsost=tabl[tsost][6]; break;

case '7': slsost=tabl[tsost][7]; break;

case '8': slsost=tabl[tsost][8]; break;

case '9': slsost=tabl[tsost][9]; break;

case '{': slsost=tabl[tsost][10]; break;

case '}': slsost=tabl[tsost][11]; break;

case '/': slsost=tabl[tsost][12]; break;

case ';': slsost=tabl[tsost][13]; break;

case '#': slsost=tabl[tsost][14]; break;

default: slsost=1;}

printf("%5d\n",slsost);

tsost=slsost;

};

switch (slsost)

{ case 1:cout<<"\n STRING is WRONG \n"; break;

case 0:cout<<"\n STRING is RIGHT \n";break;}

return 0;

};

Реализация конечного автомата средствами ООП:

// заголовочный файл konavt.h описание класса конечного автомата

class konavt {int kolsost;// число состояний автомата

int kolsimv;// число символов входного алфавита

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

int nachstate; //начальное состояние

int kolkon;//число заключительных состояний

int *fin; //заключительные состояния

int **per;//матрица переходов

int dlina;// текущая длина входной цепочки

int dlina0;// начальная длина входной цепочки

char *vxod;// входная цепочка

int avtstate; //текущее состояние

int nomstep;// номер шага автомата

int *protokol;// протокол работы автомата

public:bool error; //признак ошибки

konavt();//конструктор без параметров

void show_sost();//проверка заполнения матрицы

void sled();//срабатывание переходов

void show();//показ текущего состояния;

void init();//инициализация новой строкой

bool konec();// проверка финальности состояния

bool zaversh(); //проверка исчерпания строки

bool proverka();// проверка принадлежности символов алфавиту

};

//Файл реализации класса автомата konavt.cpp

# include "konavt.h"

# include <iostream.h>

# include <fstream.h>

# include <string.h>

# include <stdlib.h>

//конструктор

konavt::konavt()

{int i,j,vyb;

// возможен ввод исходных данных как из файла, так и с клавиатуры

cout<<"constructor working..."<<endl;

cout <<"Istochnik dannyx(0-klaviatura,1-file)"<<endl;

cin>>vyb;

// ввод с клавиатуры

if (vyb==0)

{cout<<"\n Enter kolvo sostoianiy\t";

cin>>kolsost;

cout<<endl<<"enter kolvo simvolov alfavita\t";

cin>>kolsimv;

alfavit=new char [kolsimv];

per=new int*[kolsost];

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

per[i]=new int [kolsimv];

};

cout<<endl<<"enter alfavit"<<endl;

for (j=0;j<kolsimv;j++){

cin>>alfavit[j];

};

cout<<endl<<"enter matrica"<<endl;

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

for (j=0;j<kolsimv;j++){

cin>>per[i][j];

};

cout<<endl;

};

cout<<"enter nachalnoe sostoianie"<<endl;

cin>>nachstate;

cout<<endl;

cout<<"enter kolvo konechnyh sostoianiy"<<endl;

cin>>kolkon;

cout<<endl;

fin=new int[kolkon];

cout<<"enter konechnye sostoiania"<<endl;

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

cin>>fin[i];

}

cout<<endl;

// запись исходных данных в файл

int otv;

cout<<"save to file?(1-yes,0-no)";

cin>>otv;

cout<<endl;

if (otv==1)

{char fname[30];

cout<<"enter filename ";

cin>>fname;

cout<<endl;

ofstream out_stream;

out_stream.open(fname);

if (out_stream.fail())

{cout<<"Error output file"<<endl; return;}

out_stream<<kolsost<<' ';

out_stream<<kolsimv<<' ';

for (i=0;i<kolsimv;i++) out_stream<<alfavit[i]<<' ';

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

for (j=0;j<kolsimv;j++){

out_stream<<per[i][j]<<' ';}}

out_stream<<nachstate<<' ';

out_stream<<kolkon<<' ';

for (i=0;i<kolkon;i++)out_stream<<fin[i]<<' ';

out_stream.close();

cout<<"End of output file..."<<endl;

};

} else

// ввод исходных данных из файла

{ char filename[30];

cout<<"Enter Filename ";

cin>>filename;

cout<<endl<<"vvedeno "<<filename<<endl;

ifstream in_stream;

in_stream.open(filename);

if (in_stream.fail())

{cout<<"net faila "<<filename<<endl; return;

};

in_stream>>kolsost;

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

in_stream>>kolsimv;

cout<<"kolsimv="<<kolsimv<<endl;

alfavit=new char[kolsimv];

for (i=0;i<kolsimv;i++){ in_stream>>alfavit[i];};

for (i=0;i<kolsimv;i++) cout<<alfavit[i]<<" ";

cout<<endl;

per=new int*[kolsost];

for (i=0;i<kolsost;i++)per[i]=new int [kolsimv];

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

for (j=0;j<kolsimv;j++){

in_stream>>per[i][j];}}

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

for (j=0;j<kolsimv;j++){

cout<<per[i][j];}cout<<endl;}

in_stream>>nachstate;

cout<<"begin state "<<nachstate<<endl;

in_stream>>kolkon;

cout<<"Number of end states "<<kolkon<<endl;

fin=new int[kolkon];

for (i=0;i<kolkon;i++)in_stream>>fin[i];

for (i=0;i<kolkon;i++)cout<<fin[i]<<" ";

cout<<endl;

in_stream.close();

cout<<"End of output file..."<<endl;

}

return;};

//показ текущего состояния

void konavt::show_sost()

{int i;

cout<<"sostoyanie "<<avtstate<<endl;

cout<<dlina<<endl;

//cout<<"ostatok vxoda "<<vxod<<endl;

cout<<"ostatok vxoda ";

//for (i=0; i<dlina;i++) cout<<vxod[i]<<"\t"; // *(vxod+i)

//cout<<endl;

for (i=0; i<dlina;i++) cout<<*(vxod+i)<<"\t";

cout<<endl<<"protokol ";

for (i=0;i<dlina0+1;i++) cout<<protokol[i]<<"\t";

cout<<endl;

};

//переход к следующему состоянию

void konavt::sled()

{int slsost,i,num;

num=-1;

char teksimv;

teksimv=vxod[0];

cout<<"symbol "<<teksimv<<endl;

for (i=0;i<kolsimv;i++) if (teksimv==alfavit[i]) {num=i;break;};

if (num==-1){cout<<"illegal symbol "<<teksimv<<endl;error=true;}

else {slsost=per[avtstate][num];

avtstate=slsost;

protokol[nomstep]=slsost;

nomstep++;

for (i=0;i<dlina;i++)vxod[i]=vxod[i+1];

vxod[dlina-1]=' ';

dlina=dlina-1;

};

return;};

//проверка допустимости входной строки

bool konavt::proverka()

{int i,j;

bool prizn;

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

{prizn=false;

for (j=0;j<kolsimv;j++) if (vxod[i]==alfavit[j]) {prizn=true;break;};

if (!prizn) {cout<<"illegal symbol "<<endl;break;};

};

return prizn;

};

//ввод новой входной строки

void konavt::init()

{int i;

cout<<"enter dlina"<<endl;

cin>>dlina;

dlina0=dlina;

vxod=new char[dlina+1];

protokol=new int [dlina+1];

for (i=0;i<dlina+1;i++)protokol[i]=0;

cout<<endl<<"enter vhodnaya stroka"<<endl;

for (i=0;i<dlina;i++)cin>>vxod[i];

//vxod[dlina]='\0';

cout<<endl;

//cout<<"ostatok vxoda "<<vxod<<endl;

cout<<"ostatok vxoda ";

for (i=0; i<dlina;i++) cout<<vxod[i]<<"\t";

cout<<endl;

if (proverka()) {avtstate=nachstate;

protokol[0]=nachstate;

nomstep=1;

error=false;}

else error=true;

return;};

//показ параметров автомата

void konavt::show()

{int i,j;

cout<<"parametry avtomata"<<endl;

cout<<"kolvo sostoianiy "<<kolsost<<endl;

cout<<"kolvo simvolov alfavita "<<kolsimv<<endl;

cout<<"simvoly alfavita"<<endl;

for (j=0;j<kolsimv;j++){

cout<<alfavit[j]<<"\t";

};

cout<<endl<<"matrica perehodov"<<endl;

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

for (j=0;j<kolsimv;j++){

cout<<per[i][j]<<"\t";

};

cout<<endl;

};

cout<<"nachalnoe sostoianie "<<nachstate<<endl;

cout<<"konechnye sostoiania "<<endl;

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

cout<<fin[i]<<"\t";

};cout<<endl;

return;};

//проверка завершающего состояния

bool konavt::konec()

{int i;

bool kon;

kon=false;

i=-1;

for (i=0;i<kolkon;i++) if(avtstate==fin[i]){kon=true;break;};

return kon;

};

//проверка исчерпания входной строки

bool konavt::zaversh()

{bool prizn;

if(dlina==0) prizn=true; else prizn=false;

return prizn;

};

// головная программа

# include "konavt.h"

# include <iostream.h>

int main()

{

konavt tavt;

tavt.show();

int povt;

povt=1;

while (povt==1)

{tavt.init();

tavt.show_sost();

if (!tavt.error)

{do

{ tavt.sled();

tavt.show_sost();

} while (!((tavt.error)&&(tavt.zaversh())));

if ((tavt.zaversh()) && (tavt.konec()))

cout<<"\n !!!stroka prinimaetsa"<<endl;else

cout<<"\n !!!stroka ne prinimaetsa"<<endl;}

cout<<"repeat?(1,0)\n";

cin>>povt;

cout<<endl;

};

return 0;

}

Размещено на Allbest.ru