Моделирование работы конечного распознавателя
Пример выполнения курсовой работы Построить детерминированный конечный распознаватель для последовательности элементов типа «дата» в формате, удобном для сортировки (ГГГГ/ММ/ДД), разделенных точкой с запятой, при этом значение даты должно быть помещено в фигурные скобки, а год должен отображаться четырьмя символами, последовательность должна завершаться знаком «#», например… Читать ещё >
Моделирование работы конечного распознавателя (реферат, курсовая, диплом, контрольная)
Курсовая работа № 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 = (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};
Множество состояний ={ЧЕТ, НЕЧЕТ};
Функции переходов:
Начальное состояние = {ЧЕТ};
Допускающие состояния = {НЕЧЕТ}.
Простейшая программная реализация КА — контроллера нечетности:
#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) //пока не нажата клавиша
{putch (ch);
inpstr[i++]=ch;}
inpstr[i]='';
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,+78 534,-4577#);
последовательности целых чисел, разделенных точкой с запятой, и заканчивающейся символом #, например, (65;+78 534;-4577#);
последовательности целых чисел, разделенных слэшами, и заканчивающейся символом #, например, (65/+78 534/-4577#);
последовательности составных имен объектов, разделенных слэшами, и заканчивающейся символом #, т. е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w/e.w1/re.r5.а#);
последовательности составных имен объектов, разделенных точкой с запятой, и заканчивающейся символом #, т. е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w;e.w1;re.r5.а#);
последовательности составных имен объектов, разделенных запятыми, и заканчивающейся символом # - т. е. точечных нотаций идентификаторов, разделенных точками, идентификатор может содержать латинские буквы, цифры и знаки подчеркивания, а начинаться либо с буквы, либо со знака подчеркивания, например, (q.ad.w, e. w1,re.а, r5#);
полной и сокращенной спецификации файла, например (a:w1data.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. конечный автомат число программа Построение конечного автомата.
Между конечными автоматами и автоматными грамматиками существует тесная связь: класс языков, допускаемых конечными автоматами, совпадает с классом языков, порождаемых автоматными грамматиками.
Для построения конечного автомата составленную грамматику путем введения дополнительных состояний надо преобразовать к автоматному виду, в результате получится следующая таблица переходов.
{ | } | ; | # | |||||||||||||
да | ||||||||||||||||
нет | ||||||||||||||||
дата | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | год | нет | нет | нет | нет | |
год | Цг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 («matrican»);
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]='';
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 («%5dn», 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
# include
# include
# include
//конструктор
konavt:konavt ()
{int i, j, vyb;
// возможен ввод исходных данных как из файла, так и с клавиатуры
cout<<" constructor working…" <
cout <<" Istochnik dannyx (0-klaviatura, 1-file)" <
cin>>vyb;
// ввод с клавиатуры
if (vyb==0)
{cout<<" n Enter kolvo sostoianiyt" ;
cin>>kolsost;
cout<<" enter kolvo simvolov alfavitat" ;
cin>>kolsimv;
alfavit=new char [kolsimv];
per=new int*[kolsost];
for (i=0;i
per[i]=new int [kolsimv];
};
cout<<" enter alfavit" <
for (j=0;j
cin>>alfavit[j];
};
cout<<" enter matrica" <
for (i=0;i
for (j=0;j
cin>>per[i][j];
};
cout<
};
cout<<" enter nachalnoe sostoianie" <
cin>>nachstate;
cout<
cout<<" enter kolvo konechnyh sostoianiy" <
cin>>kolkon;
cout<
fin=new int[kolkon];
cout<<" enter konechnye sostoiania" <
for (i=0;i
cin>>fin[i];
}
cout<
// запись исходных данных в файл
int otv;
cout<<" save to file?(1-yes, 0-no)" ;
cin>>otv;
cout<
if (otv==1)
{char fname[30];
cout<<" enter filename «;
cin>>fname;
cout<
ofstream out_stream;
out_stream.open (fname);
if (out_stream.fail ())
{cout<<" Error output file" <
out_stream<<' ';
out_stream<<' ';
for (i=0;i<<<' ';
for (i=0;i
for (j=0;j
out_stream<<<' ';}}
out_stream<<' ';
out_stream<<' ';
for (i=0;i<<<' ';
out_stream.close ();
cout<<" End of output file…" <
};
} else
// ввод исходных данных из файла
{ char filename[30];
cout<<" Enter Filename «;
cin>>filename;
cout<<" vvedeno «<
ifstream in_stream;
in_stream.open (filename);
if (in_stream.fail ())
{cout<<" net faila «<
};
in_stream>>kolsost;
cout<<" kolsost="<
in_stream>>kolsimv;
cout<<" kolsimv="<
alfavit=new char[kolsimv];
for (i=0;i>alfavit[i]; };
for (i=0;i<<<" «;
cout<
per=new int*[kolsost];
for (i=0;i
for (i=0;i
for (j=0;j
in_stream>>per[i][j]; }}
for (i=0;i
for (j=0;j
cout<<
in_stream>>nachstate;
cout<<" begin state «<
in_stream>>kolkon;
cout<<" Number of end states «<
fin=new int[kolkon];
for (i=0;i>fin[i];
for (i=0;i<<<" «;
cout<
in_stream.close ();
cout<<" End of output file…" <
}
return;};
//показ текущего состояния
void konavt: show_sost ()
{int i;
cout<<" sostoyanie «<
cout<
//cout<<" ostatok vxoda «<
cout<<" ostatok vxoda «;
//for (i=0; i<<<" t"; // *(vxod+i)
//cout<
for (i=0; i<<*(vxod+i)<<" t" ;
cout<<" protokol «;
for (i=0;i<<<" t" ;
cout<
};
//переход к следующему состоянию
void konavt: sled ()
{int slsost, i, num;
num=-1;
char teksimv;
teksimv=vxod[0];
cout<<" symbol «<
for (i=0;i
if (num==-1){cout<<" illegal symbol «<
else {slsost=per[avtstate][num];
avtstate=slsost;
protokol[nomstep]=slsost;
nomstep++;
for (i=0;i
vxod[dlina-1]=' ';
dlina=dlina-1;
};
return;};
//проверка допустимости входной строки
bool konavt: proverka ()
{int i, j;
bool prizn;
for (i=0;i
{prizn=false;
for (j=0;j
if (!prizn) {cout<<" illegal symbol «<
};
return prizn;
};
//ввод новой входной строки
void konavt: init ()
{int i;
cout<<" enter dlina" <
cin>>dlina;
dlina0=dlina;
vxod=new char[dlina+1];
protokol=new int [dlina+1];
for (i=0;i
cout<<" enter vhodnaya stroka" <
for (i=0;i>vxod[i];
//vxod[dlina]='';
cout<
//cout<<" ostatok vxoda «<
cout<<" ostatok vxoda «;
for (i=0; i<<<" t" ;
cout<
if (proverka ()) {avtstate=nachstate;
protokol[0]=nachstate;
nomstep=1;
error=false;}
else error=true;
return;};
//показ параметров автомата
void konavt: show ()
{int i, j;
cout<<" parametry avtomata" <
cout<<" kolvo sostoianiy «<
cout<<" kolvo simvolov alfavita «<
cout<<" simvoly alfavita" <
for (j=0;j
cout<<<" t" ;
};
cout<<" matrica perehodov" <
for (i=0;i
for (j=0;j
cout<<<" t" ;
};
cout<
};
cout<<" nachalnoe sostoianie «<
cout<<" konechnye sostoiania «<
for (i=0;i
cout<<<" t" ;
};cout<
return;};
//проверка завершающего состояния
bool konavt: konec ()
{int i;
bool kon;
kon=false;
i=-1;
for (i=0;i
return kon;
};
//проверка исчерпания входной строки
bool konavt: zaversh ()
{bool prizn;
if (dlina==0) prizn=true; else prizn=false;
return prizn;
};
// головная программа
# include «konavt.h»
# include
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" <
cout<<" n!!! stroka ne prinimaetsa" <
cout<<" repeat?(1,0)n" ;
cin>>povt;
cout<
};
return 0;
}