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

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

Размещено на

Курсовая работа № 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».

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

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

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

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

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

...