Курсовая работа: Моделирование работы конечного распознавателя для последовательно-сти элементов типа "дата" в немецком формате, разделенных запятыми и заключённых в фигурные скобки

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

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

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

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

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

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

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

.

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

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

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

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

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