Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Определение, способы представления конечного автомата




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Конечный автомат содержит управляющее устройство, входной и выходной каналы. Для управляющего устройства выделено начальное состояние q0. Работа автомата осуществляется в дискретные такты времени t= 1, 2, 3, …. На входной канал автомата последовательно поступают символы x1, x2, …, при этом управляющее устройство изменяет свое состояние, а на выходе появляются выходные символы y1, y2, …. Работа автомата определяется системой команд, каждая из которых имеет вид qixr ® qjys, где qi, qj – внутренние состояния автомата, xr – входной символ, ys – выходной символ. Обычно требуют, чтобы выполнялось условие однозначности, т.е. не может быть двух команд с одинаковыми левыми и различными правыми частями. Такой автомат называется детерминированным. Выходной символ, вырабатываемый автоматом, зависит не только от входного символа на текущем такте времени, но и от внутреннего состояния. В свою очередь, внутреннее состояние автомата зависит от входных символов, поступивших в предыдущие такты времени. В этом смысле автомат обладает памятью.

Дадим формальное определение конечного автомата. Конечный автомат M=(Q, X, Y, d, l), где Q={q0, q1, …, qk} – конечное множество внутренних состояний автомата, X={x1, x2, …, xn} – множество входных символов (входной алфавит), Y={y1, y2, …, ym} – множество выходных символов (выходной алфавит), d(q,x) : Q´X ® Q – функция переходов автомата из одного состояния в другое, l(q,x) : Q´X ® Y – функция выходов. Состояние автомата соответствует памяти о прошлом, позволяя устранить время как явную переменную. Автомат обычно задают таблицей переходов, в заголовках строк которой стоят все возможные состояния автомата, в заголовках столбцов – все символы входного алфавита, а на пересечениях строк и столбцов – следующее состояние автомата и выходной символ.

Пример 5.1. Рассмотрим таблицу переходов некоторого автомата с входным алфавитом X={a, b}, выходным алфавитом – Y={b, c}, множеством состояний Q={q1, q2, q3}.

a b
q1 q2, c q3, c
q2 q1, b q2, c
q3 q2, b q1, b

 


Пусть на вход автомата поступает последовательность символов a, a, b, a. Рассмотрим работу автомата: .
На выходе автомата получится последовательность c, b, c, b.

Автомат можно также наглядно задать с помощью ориентированного мультиграфа, называемого графом переходов состояний. Вершины этого графа соответствуют состояниям, дуга ведет из вершины qi в вершину qj, если d(qi, xr)=qj и l(qi, xr)=ys, причем каждой дуге приписана пара xr, ys. Кратные дуги из вершины qi в вершину qj заменяются одной дугой, которой приписаны несколько пар входной – выходной символы.

Пример 5.2. Построим граф переходов состояний для примера 5.1.

 

q3
q1
q2
a,c
a,b
b,c
a,b
b,b
b,c

Не любой ориентированный мультиграф, все дуги которого помечены подобным образом, соответствует некоторому автомату. Для соответствия автомату в каждой вершины qi должны выполняться следующие два условия:

1) для любого входного символа xr имеется дуга, выходящая из qi и помеченная xr (условие полноты);

2) любой символ xr встречается только на одной дуге, выходящей из qi (условие детерминированности).

11,0
q0
q1
00,1
01,0
10,0
11,1
01,1
10,1
00,0

Пример 5.3. Построим граф переходов для двоичного сумматора, который по данным двум n-разрядным двоичным числам вычисляет их сумму. Входные данные начинаются с битов с наименьшими значениями, пары битов читаются справа налево.

Двойная окружность на вершинах означает, что эти состояния – заключительные. Пусть суммируются числа 011010 и 001100. Тогда на вход автомата поступает последовательность 00, 10, 01, 11, 10, 00. Рассмотрим работу автомата:

.

На выходе автомата получим последовательность 0, 1, 1, 0, 0, 1.







Дата добавления: 2015-09-18; просмотров: 323. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.01 сек.) русская версия | украинская версия