Примеры конечных автоматов

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты).

- детерминированный

- недетерминированный

- автомат Мили(генератор)

Текст лекции

ПРИМЕРЫ КОНЕЧНЫХ АВТОМАТОВ. (до 90 минут)

Автомат Мили

Выходной символ автомата Мили в момент времени t определяется функцией выходов

w (t)= m [ s (t), v (t)]. (3)

Таким образом, функция выходов автомата Мили реализует отображение некоторого подмножества D_m Í S ´ V декартова произведения S ´ V в множество W. Иногда, для краткости используют обозначение: s⁺ = s (t +1), s = s (t), v = v (t), w = w (t). Тогда функция переходов автомата Мили запишется в виде s⁺ = l (s, v), а функция выходов в виде w = m (s, v).

Автомат называется полностью опредленным, если D_l = D_m = S ´ V. В противном случае автомат называется частичным. Иными словами, у полностью определенного автомата области определения функций l [×,×] и m [×,×] совпадают с декартовым произведением S ´ V, а у частичного автомата эти функции определены на подмножествах D_l и D_m множества S ´ V.

Способность автомата фиксировать состояния, представляющие классы входных последовательностей (события), называют памятью автомата. Каждое состояние s Î S автомата представляет некоторый класс эквивалентности { v (0) v (1) v (2)… v (k)} _s входных последовательностей, поскольку поведение автомата в любой момент времени t зависит только от класса, т.е. s (t), и входного воздействия v (t). Такой подход позволяет устранить время как явную переменную и выразить выходные символы как функцию состояний и входных символов в данный момент времени, что находит выражение в общей записи модели A абстрактного автомата Мили:

A = < V,W,S,l,m,s (0)>, (4)

где

V,W,S - алфавиты входных, выходных символов и символов состояний соответственно;

Автомат Мура

Абстрактный автомат Мура это частный случай автомата Мили (4), когда выходной символ зависти только от сосояния автомата, а именно функция выходов автомата Мура:

w = m (s) (5)

Для каждого автомата Мили можно построить эквивалентный автомат Мура, реализующий точно такой же алфавитный оператор. Пусть A = < V,W,S,l,m,s (0)> автомат Мили. В качестве состояний эквивалентного автомата Мура возьмем пары . Тогда функция выходов эквивалентного автомата Мура

, (6)

а функция переходов

. (7)

l, m - функции переходов и выходов соответственно;

s (0) - начальное состояние.

1.

- детерминированный, инициальный, логический, всюду определенный, преобразователь А^* ® В^* (автомат Мили)

2.

- недетерминированный по переходам, детерминированный по выходам, инициальный, частично определенный преобразователь.

3.

<{a1,a2},{q0,qz},{b1,b2},q,d,t>-детерминированный по переходам,недетерминированный по выходам инициативный преобразователь - определенный.

QXA d Q

QXA t B

4.

<{a1,a2},{q0,qz},{b1,b2},q,t>-недетерминированный, всегда определенный преобразователь.

QXA t1 Q

QXA t2 B

5.

<{a},{q1,q2,q3},{b1,b2},d,l>-автономный автомат Мили(генератор)

6.

<{a1,a2},{q1,q2,q3},{b1,b2},d,l>-автомат Мура

7.

логический автомат Мили без выходов(акцептор)<{a,1},{q0,q1},d>

8.

комбинационный автомат,эквивалентный автомат без памяти

Алгоритм преобразования недетерминированного конечного автомата к детерминированному виду.

Шаги алгоритма преобразования недетерминированного автомата <A,Q,P,d> в эквивалентный детерминированный акцептор < A,Q^|, q0, d> следующие:

1. Q^|=B(Q)-Æ,| Q^||=2ⁿ-1,B(Q)-булеан

2. d(q_i,a)=q_j,i=1,m, j=1,k

3. q0=q0^|

4. Множество конечных состояний детерминированного автомата строится из всех состояний, имеющих […,f_i,…], где f_i конечное состояние детерминированного акцептора.

5. Из построенного акцептора удаляют все недостижимые состояния. Доказано,что рассматриваемый алгоритм строит детерминированный акцептор, эквивалентный заданному недетерминированному распознавателю.

Пример

Заданный автомат является недетерминированным внутренними состояниями. Поэтому | Q^||=2ⁿ-1 =15

1.
B(Q)\Æ={q1}U{q2}U{q3}U{q3}U{q4}U{q1,q2}U{q1,q3}U{q1,q4}U{q2,q3}U{q2,q3}U{q2,q4}U{q3,q4}U{q1,q2,q3}U{q1,q2,q4}U{q1,q3,q4}U{q2,q3,q4}U{q1,q2,q3,q4}.

2. Cтроим ф-ию переходов:

d(q1,a2)=q3,

d(q3,a1)=q2,

d(q2,a2=(q3,q4),

d({q1,q3},a1)=q3, d({q1,q2},a2)=(q3,q4)

d({q1,q4},a2)=q3

d({q1,q4},a2)=q3

d({q2,q3},a1)=q2

d({q2,q3},a2)=(q3,q4)

d({q2,q4},a2)=(q3,q4)

d({q3,q4},a1)=q2

d({q1,q2,q3},a10=q2

d({q1,q2,q3},a2)={q3,q4}

d({q1,q2,q4},a2)=(q3,q4)

d({q1,q3,q4},a2)=q3

d({q1,q3,q4},a1)=q2

d({q2,q3q4},a1)=q2

d({q2,q3,q4},a2)=(q3,q4)

d({q1,q2,q3,q4},a1)=q2

d({q1,q2,q3,q4},a2)=(q3,q4)

3. Аналогичное состояние эквивалентного акцептора q0^|=q1

4. Множество конечных состояний F эквивалентного автомата F={qz,(q1,qz),(q2,qz),(q3,qz),(q,q2,qz),(q1,q3,qz),(q2,q3,qz),(q1,q2,q3,qz)

5. Удаляем недостижимые вершины графа, недостижимыми вершинами являются, те состояния которых при каком-то aÎА* невозможен переход из q0,построенного детерминированного автомата следующим:(q1,q2),(q1,q3),(q1,q4),q4,(q1,q2,q3),(q1,q2,q4),(q2,q3,q3),(q1,q3,q4),(q1,q2,q3,q4),(q2,q3), (q2,q4).

Исходный акцептор

<{a1,a2},{q1,q2,q(3,q4)=qz}/q1=q0,d> имеет следующий граф переходов:

Этот распознаватель является не всюду определенным.

Замечание

·

Детерминированный частичный конечный автомат можно преобразовать в автомат Мили, если ввести фиктивное состояние на которое заменяют все неопределенные переходы. В качестве примера преобразования частичного автомата в автомат всюду определенный,рассмотрим полученный граф переходов детерминированного акцептора. Имеем следующий автомат Мили:

Моделировать работу автомата Мили существенно проще, чем работу произвольного конечного автомата.Однако, следует учитывать и затраты на моделирование автомата Мили, которые больше, чем затраты на моделирование недетерминированного частичного автомата.

Лекция №4.

Поведение конечных автоматов

Тренарное отношение

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

- функции перехода, выхода

- процессы преобразования, распознавания, порождения.

Текст лекции

Дата добавления: 2015-12-01