ДМ КУРСАЧ Настя
.docx8 вариант Настя
Задание 4.
Формулировка задания:
Изобразим таблицу данного автомата.
A Q |
1 |
2 |
3 |
4 |
a |
2,0 |
4,1 |
4,0 |
4,0 |
b |
1,0 |
3,0 |
2,1 |
3,0 |
По данному неинициальному автомату Мили S строим эквивалентный ему автомат Мура S’ следующим образом:
Автомат S’ содержит 4*2+4=12 состояний, каждое из которых мы будем помечать двумя символами. Состояния автомата S’ обозначим так: *1, *2, *3, *4, a1, b1, a2, b2, a3, b3, a4, b4.
Функция отметок μ на состояниях *1, *2, *3, *4 не определена, а ее значения на состояниях a1, b1, …, b4 задаются с помощью функции выходов λ автомата S: , где 1≤i≤4, u⸦{a,b}. То есть μ(a1)=λ(a,1)=0, …, μ(b4)=λ(b,4)=0.
Функция переходов δ’ на состояниях, содержащих в изображении символ *, определяется так: δ’(u,*i)=ui, u⸦{a,b}, 1≤i≤4.
В остальных случаях первый символ имени нового состояния совпадает со считываемым символом входного автомата, а второй символ нового состояния определяется с помощью функции переходов δ автомата S: δ’(u,vi)=vi, где u,v⸦{a,b}, j=δ(v,i).
Получим: δ’(a,*1)=a1, δ’(b,a1)=b2, т.к. δ(a,1)=2, и т.д.
Запишем таблицу состояний полученного автомата Мура.
μ |
- |
- |
- |
- |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
A Q |
*1 |
*2 |
*3 |
*4 |
a1 |
b1 |
a2 |
b2 |
a3 |
b3 |
a4 |
b4 |
a |
a1 |
a2 |
a3 |
a4 |
a2 |
a1 |
a4 |
a3 |
a4 |
a2 |
a4 |
a3 |
b |
b1 |
b2 |
b3 |
b4 |
b2 |
b1 |
b4 |
b3 |
b4 |
b2 |
b4 |
b3 |
Проверим работу исходного автомата над словом abbb, запустив его из 2 состояния:
|
a |
b |
b |
b |
b |
2 |
4 |
3 |
2 |
3 |
2 |
|
1 |
0 |
1 |
0 |
1 |
Построенный автомат Мура запускаем из состояния *1:
|
a |
b |
b |
b |
b |
*2 |
a2 |
b4 |
b3 |
b2 |
b3 |
|
1 |
0 |
1 |
0 |
1 |
Как видим, результаты обоих автоматов совпали.