 |
Способы задания функций переходов.
|
|
|
|
Существует три способа:
1. перечисление
2. табличный
3. графический
a) При перечислении приводятся все значения функции переходов
S1 = φ(S0, P1)
S2 = φ(S1, P2)
......
Sm = φ(Sm-1, Pi)
b) При табличном способе столбцы помечаются входными буквами, строки – буквы состояний из которых осуществляется переход.
Внутри таблицы на пересечении строки и столбца указывается состояние в который переходит автомат.
| Pi | P1 | P2 | ….. | Pn |
| Sj | ||||
| S0 | S1 | S2 | ….. | S1 |
| S1 | S0 | S2 | ….. | Sm |
| ….. | ….. | ….. | ….. | …… |
| Sm | ….. |
c) Графический
Каждому состоянию автомата ставится в соответствие вершина графа, которая помечается символом состояния.
Между состояниями присутствует дуга – если между ними есть переход.
Направление дуги указывает направление перехода – ориентированный граф, а сама дуга помечается буквой входного алфавита под воздействием которого и осуществляется данный переход.
 | |||
 | |||
Пример:
S0 = φ(S0, P1)
S1 = φ(S0, P2)
S1 = φ(S1, P1)
S2 = φ(S1, P2)
S2 = φ(S2, P1)
S0 = φ(S2, P2)
| Pj | P1 | P1 | ||
| Sj | ||||
| S0 | S0 | S1 | ||
| S1 | S1 |
| ||
| S2 | S2 | S0 |
 |
| t0 | t1 | t2 | t3 | t4 | t5 | t6 | t7 | машинные такты |
| P1 | P2 | P1 | P1 | P2 | P1 | P2 | входное слово | |
| S0 | S0 | S1 | S1 | S1 | S2 | S2 | S0 | последовательность состояний |
Автоматы (с выходным преобразователем)
Они представляют собой совокупность следующих шести объектов
A = <P, S, s0, φ, W, ψ>
W – выходной алфавит
ψ – функция выходов
Существует две математические модели автомата(автомат Мура и Миля) обе мобели можно представить виде двух частей – формулирователь предыстории и выходного преобразователя.
Автомат Мура:
 |
|
|
|
В автомате Мура осуществляется отображение S -> W, т.е. каждой букве состояния ставится буква выходного алфавита.
Wi = ψ(si)
Wi (t+1)= ψ(s(t+1)) – новый выходной символ определяется новым состоянием.
Автомат Миля:
 |
осуществляется отображение P * S -> W. т.е.
Wk = ψ(Pi, Sj)
W(t+1) = ψ(P(t), S(t))
Новое выходное слово в автомате Миля определяется состоянием, в котором был автомат и выходным словом, который поступил на автомат.
Был в состоянии -> поступил в состояние.
Способы задания автоматов
Задание автомата Мура:
A: <P, W, S, s0, φ, ψ>
В автомате Мура ψ зависит только от состояний.
Автомат как Мура, так и Миля задается шестью параметрами.
P, W, S – задаются в виде множеств
s0 – начальное состояние указывается как буква алфавита S
Функция φ – задается тремя способами (рассмотренными ранее): перечисление, табличный, графический.
Функция ψ – также может быть представлена теми же тремя способами.
Автомат Мура:
a) перечисление
φ: S1 = φ(S0, S1) ψ: W1 = ψ (S1)
φ: S2 = φ(S1, S1) ψ: W2 = ψ (S2)
….. …..
φ: Sk = φ(Sk, Sk-1) ψ: W0 = ψ (S0)
b) табличный способ
φ, ψ
| Wi | Pi | Pi | P0 | P1 | P2 | … | Pn-1 |
| Si | |||||||
| W0 | S0 | Si | Sj | … | … | … | … |
| W1 | S1 | … | … | … | … | … | … |
| Wl-1 | Sm-1 | S0 | Sk | .. | … | … | … |
Данная таблица одна определяет две функции, так как Wi зависит только от Si
Таблица называется «отмеченной» таблицей.
Количество W и S может быть разное, т.к. разным состояниям может быть поставлено в соответствие одна и та же выходная буква.
c) графический способ
 |
Пример (автомат Мура)
P = {P1, P2} – входной алфавит
W = {W0, W1} – выходной алфавит
|
|
|
S = {s0, s1, s2, s3 } – алфавит состояний
s0 – начальное состояние
Функция переходов:
S0 = φ (S0, P1)
S0 = φ (S3, P2)
S1 = φ (S0, P2)
S2 = φ (S1, P1)
S2 = φ (S2, P1)
S3 = φ (S1, P2)
S3 = φ (S2, P2)
S3 = φ (S3, P1)
Функция выходов:
W0 = ψ (S0)
W1 = ψ (S1)
W0 = ψ (S2)
W0 = ψ (S3)
Табличный способ:
| Wi | Pi | P1 | P2 |
| Si | |||
| W0 | S0 | S0 | S1 |
| W1 | S1 | S2 | S3 |
| W0 | S2 | S2 | S3 |
| W0 | S3 | S3 | S0 |
Графический способ:
| ti | t0 | t1 | t2 | t3 | t4 | |
| si | s0 | s0 | s1 | s3 | s3 | s0 |
| Pi | P1 | P2 | P2 | P1 | P2 | |
| Ni | * | W0 | W1 | W0 | W0 | W0 |
* - эта ячейка пуста, т.к. W(t+1) = ψ(s(t+1)) – это не реакция на входной сигнал
В момент t0 значение Wi не считывается, т.к. отсутствовал входной сигнал, в то время как выходная последовательность должна быть реакцией на входную.
На выходе автомата тем не менее будет значение W0, т.к. выход однозначно определяется состоянием автомата Мура, а состояние = S0.
Для полной проверки автомата необходимо послать такую последовательность P, чтобы автомат прошел по всем переходам при всех входных сигналах, желательно чтобы автомат оказался в начальном состоянии S0, что позволит подавать новые входные последовательности без предварительной начальной установки.
|
|
|
