Структурні автомати

Практичне завдання
Мета: Розглянути структурні автомати, основні властивості та вирішити задачі.
Задачі
1. Описати у вигляді кінцевого автомата (таблиця і діаграма) елемент
«або-ні» і елемент «об'єднання проводів» з алфавітами входу і виходу, описаними вище.
2. Скласти структурний автомат «ні» з автоматів вище – зобразити схему з'єднання, перерахувати стани входів та виходів кожного з внутрішніх автоматів та автомата загалом при подачі на вхід 0 та 1.
3. Нехай у ланцюжок з'єднані автомати-повторювачі (що видають на вихід те, що подали на вхід), що працюють із затримкою – що змінюють свій стан на виході через час після зміни входу. Нехай спочатку на всіх входах і виходах Опишіть, що станеться, якщо подати на вхід першого 1? А що відбуватиметься, якщо почати змінювати сигнал на вході першого елемента сигнал із 0 на 1 і назад з періодом ?
А якщо подати 1 на час , потім 0 на 3 потім знову 1 на і т.д.?
4. Вибрати будь-яку з чотирьох таблиць для стратегії, що враховує тільки останній хід противника, і описати таку стратегію як кінцевого автомата (на вхід надходить минулий хід противника, на виході повинен з'являтися поточний хід стратегії).
5. Скільки очок набере обрана вами стратегія за 5 ходів, якщо вважати, що противник повертає на наступному кроці те, що вона видала на виході на цьому кроці. Перший хід стратегії (до отримання інформації про ходи співгравця) та противника виберіть та вкажіть.
Вирішення
1) Перш за все запишемо алфавіти входу та виходу:
Алфавіт входу: {00, 01, 10, 11}
Алфавіт виходу: {0, 1}
Тепер побудуємо елемент «або-ні», використовуючи мову автомата Мура

Тепер побудуємо таблицю переходів та виходів для елемента:
I/O
S
1
/0
S
2
/1
S
3
/1
S
4
/0
00
S
3
-
-
-
01
-
S
4
-
-
10
-
S
4
-
-
11
-
S
4
-
-
Так само побудуємо діаграму і таблицю для елементу «Об’єднання проводів».
Алфавіт входу: {0,1}
Алфавіт виходу: {00,11}
Елемент «Об'єднання проводів» на мові автомату Мура:
I/O
S
1
/00
S
2
/11
0
00
-
1
-
11 2) У рамках цього завдання побудуємо структурний автомат «ні» із автоматів у першому завданні. Створимо схему з’єднання перерахуємо стани
S
1
/0
S
2
/1 00 01 10 11 1
0
S
3
/1
S
4
/0 0
1
S
1
/00
S
2
/11 0
1 00 11

входів та виходів кожного з внутрішніх автоматів та автомата загалом при подачі на вхід 0 та 1(Алфавіт входу: {0, 1}).
Елемент «ні»
Вх
Вх
1
Вих
1
Вх
2
Вих
2
Вих
0
0 00 00 1
1
1
1 11 11 0
0
3) Для даної ситуації, якщо подати на вхід першого 1, то на виході буде 0 доти, доки не пройде час
t

, після чого сигнал на виході стане 1. Тоді на вхід наступного автомата буде подано 1. Через
t
 після сигнал на виході зміниться з 0 на 1 і на вхід наступного автомата потрапить 1 і т.д. Тобто кожен автомат змінюватиме свій сигнал виходу через
t

від часу зміни попереднього і від n
t

від часу подачі на перший автомат (n – номер автомата)
Якщо почати змінювати сигнал на вході першого автомата з 1 на 0 і назад з проміжком
t

, то згодом, коли сигнал дійде до останнього автомата встановиться такий стан, при якому на вході та виході кожного з автоматів будуть різні сигнали: якщо на вході першого 1, то на виході в цей момент буде 0 тоді цей 0 буде входом другого автомата, а його вихід буде 1, що буде входом для третього і т.д.
S
1
/0
S
2
/1 1
0
S
3
/1 0
S
4
/0 1
«об'єднання проводів»
«або-ні»
00 11 1
0
Вх
Вх
1
Вих
1
Вх
2
Вих
2
Вих
S
1
/00
S
2
/11 0
1 00 11 0
1

Якщо подати 1 на
t

потім 0 на 3
t

і потім 1 на
t

і т.д., то по ланцюгу поступово буде просуватися сигнал 1000 з періодом 4
t

, тобто
1000100010001…
4) У якості обраної стратегії виберемо варіант (0,0). Тобто гравець весь час буде обирати 0.
Останній хід
противника
0 1
Відповідь
0 0
I/O
S
1
/0
S
2
/0
0
S
2
—
1
—
S
1 5) Спершу наведемо таблицю:
Участники 1↓ 2→
0 (эгоизм)
1 (
альтруизм)
0 (эгоизм)
1, 1 5, 0 1 (
альтруизм)
0, 5 3, 3
У якості обраної стратегії для гравця 2 варіант (0,0).
Останній хід
противника
0 1
Відповідь
0 0
Гравець 1 – противник, перший хід обох гравців 1.
1-ий хід гравець 1: 1 1-ий хід гравець 2: 1
Рахунок: 3*3
2-ий хід гравець 1: 1 2-ий хід гравець 2: 0
Рахунок: 3*8
3-ий хід гравець 1: 0
S
1
/0 0
S
2
/0 1