Материал: discrete_mathematics

Завдання для самостійної роботи

1.Побудувати таблиці переходів і виходів, граф автомата P, що за допомогою своїх станів запам'ятовує три останні символи (двійкові розряди), які було подано на його вхід. Вихідним сигналом є останній символ, що "забувається".

2.Побудувати таблиці переходів і виходів, граф автомата B, на виході якого з'являється сигнал 1 тоді й лише тоді, коли на його вхід була подана послідовність символів, що відповідає числовій константі – дійсному числу зі знаком і фіксованою крапкою; в іншому разі вихідним сигналом є 0. Вхідні сигнали

автомата B: x1 – знак, x2 – цифра, x3 – крапка, x4 – будь-який інший символ.

3.Побудувати автомат затримки, тобто такий, вихідний сигнал якого в момент часу t + 1 дорівнює вхідному сигналу в мо-

мент часу t, X = Y = {0, 1}.

4.Побудувати автомат для X = Y = {0, 1}, на виході якого з'являється сигнал 1 тоді й лише тоді, коли п'ять останніх вхідних сигналів – це 01101.

5.Побудувати генератор парності, тобто автомат, що функціонує в алфавітах X = Y = {0, 1} і реалізує такий алгоритм. На його вхід надходять слова довжиною 3, розділені якимось симво-

лом a, a X. На виході автомат має повторити вхідну трійку символів, замінивши розділовий символ a на 1 тоді й лише тоді, коли кількість одиниць у даній трійці парна.

6.Побудувати автомат, що перевіряє відповідність лівих і правих дужок у вхідному слові, яке задає певний алгебричний вираз. Найбільша дозволена вкладеність дужок – n. Вхідні сиг-

нали автомата: x1 – ліва дужка, x2 – права дужка, x3 – будь-який інший символ, x4 – символ, що позначає кінець виразу.

7.Побудувати автомат, що керує роботою ліфта в чотириповерховому будинку. Станами автомата є номери поверхів. Вхідний сигнал – номер потрібного поверху, вихідний сигнал – напрямок руху (угору, униз, не рухатись).

206

5.2. Автоматне відображення

Нехай у процесі функціонування заданого автомата A вхідний сигнал у момент автоматного часу t = 1 дорівнює xi1 X, у

наступний момент t = 2 – xi2 X і т. д., а в момент t = k на вхід автомата A подається сигнал xik X. Інакше кажучи, x(1) = xi1, x(2) = xi2, …, x(k) = xik. У такому разі говоритимемо, що на вхід автомата A подано вхідне слово xi1xi2…xik X*.

Для заданого автомата A його функції переходів δ і виходів λ можна природно поширити з множини U × X на множину U × X*, даючи змогу визначати стан і вихідний сигнал у автоматі A після подання на його вхід довільного вхідного слова p = xi1xi2…xik X*. Вважатимемо, що

δ(al, p) = δ(δ(…(δ(δ(al, xi1), xi2), …), xik – 1), xik),

λ(al, p) = λ(δ(…(δ(δ(al, xi1), xi2), …), xik – 1), xik).

Іноді розширені функції переходів і виходів автомата поз-

начають особливим чином, наприклад δ* і λ*, але ми цього не робитимемо й залишимо для розширених функцій ті самі позначення, що й для основних.

Розширену функцію переходів δ можна також означити індуктивно:

1)δ(al, x) для x X визначають за таблицею переходів автомата A;

2)для довільного слова p X* і довільного вхідного сигналу

x X δ(al, px) = δ(δ(al, p), x).

Спираючись на останнє означення, розширену функцію ви-

λ(al, e) = e.

Нехай A/a1 – ініціальний автомат. Для довільного вхідного слова p = xi1xi2…xik означимо відповідне вихідне слово q Y* так: q = λ(a1,x1 )λ(a1,xi1 , xi 2 )λ(a1, xi1 , xi 2 , xi 3 )...λ(xi1 , xi 2 ... xi k ).

207

Так означену відповідність між вхідними словами p і вихідними словами q називають автоматним відображенням, що індукується (ініціюється, реалізується) автоматом A/a1; позначають ϕA. Рівносильним означенням автоматного відображення ϕA : X* → Y* є такі рекурентні співвідношення:

ϕA(e) = e, ϕA(px) = ϕA(p)λ(a1, px), p X*, x X. (5.3)

Автоматне відображення часто називають також поведін кою, або зовнішньою поведінкою, автомата.

Автоматне відображення має дві важливі властивості, що випливають безпосередньо з його означення:

1)|p| = |ϕA(p)| для будь-якого слова p X*. Через |w | позначено довжину слова w.

2)Якщо p = p1p2 і ϕA(p) = q1q2, де | p1 | = |q1|, то q1 = ϕA(p1).

Назвемо сформульовані властивості умовами автоматності

відображення ϕA.

Поняття автоматного відображення можна узагальнити, аналогічно означивши відповідність між вхідними й вихідними словами, індуковану автоматом A/ai, тобто автоматом A, що починає роботу зі стану ai. Позначатимемо таке автоматне відображення через ϕAi.

Із наведених означень і умов автоматності випливає важлива властивість автоматних відображень ϕAi: якщо p = p1p2 X* і ai1 = δ(ai, p1), то

Усі наведені означення можна наочно проілюструвати за допомогою графа автомата. Якщо зафіксувати деякий стан ai U у автоматі A, то будь-яке слово p = xi1xi2…xik X* однозначно ви-

значає шлях довжиною k, що веде з вершини ai і складається з k дуг, позначених послідовно вхідними сигналами xi1, xi2, …, xik.

Тоді стан δ(ai, p) – остання вершина цього шляху, λ(ai, p) – вихідний сигнал, яким позначено останню його дугу, а ϕAi(p) – слово, утворене з послідовності k вихідних сигналів, які написані на k дугах шляху.

Приклад 5.2. Для автомата дорожнього руху D із прикладу 5.1(1) і для вхідних слів p1 = x1x1x2 та p2 = x2x2x1x2 маємо:

208

δ(a1, p1) = a3, δ(a3, p1) = a5, δ(a4, p2) = a1,

λ(a1, p1) = y3, λ(a4, p2) = y1, λ(a2, p2) = y3.

Крім того,

ϕD(p1) = y2y1y3, ϕD(p2) = y3y4y2y3,

ϕD2(p1) = y1y2y3, ϕD4(p2) = y2y3y4y1.

Для автомата-пошуковця S із прикладу 5.1 (4) матимемо:

δ(0, 0100101) = 2, δ(3, 10101100) = 1, λ(1, 0100101) = 0, λ(3, 1010110) = 1, ϕS(0100101) = 0000000, ϕS(1010110110) = 0000001001. ◄

Завдання для самостійної роботи

1.Дати індуктивне означення розширеної функції виходів.

2.За допомогою методу математичної індукції довести умови

автоматності для автоматного відображення ϕA.

3.Методом математичної індукції за довжиною слова p2 довести властивість (5.4) автоматного відображення.

4.Знайти значення автоматного відображення ϕD на даному вхідному слові для автомата дорожнього руху D із прикладу

5.1(1):

(а) ϕD1(x1x2x1x1x2); (б) ϕD1(x2x1x1x2x2x2); (в) ϕD2(x2x1x2x2x2x1x2x1x2).

5. Знайти значення автоматного відображення ϕS на вхідному слові для автомата S із прикладу 5.1 (2):

(а) ϕS1(x1x2x1x3x2); (б) ϕS1(x2x1x1x4x2x2); (в) ϕS2(x2x4x2x4x2x3x2x1x2).

5.3. Ізоморфізм і невідрізнюваність автоматів

Нехай A1 = (X, Y, U1, δ1, λ1) і A2 = (X, Y, U2, δ2, λ2) – скінченні автомати. Взаємно однозначне відображення γ:U1 → U2 називають

ізоморфізмом (або ізоморфним відображенням) автомата A1 на автомат A2, якщо для будь-яких x X1 і a U1 виконуються умови

γ (δ1(a, x)) = δ2(γ(a), x), λ1(a, x)) = λ2(γ(a), x). (5.5)

Автомати, для яких існує ізоморфізм, називають ізо морфними.

209

Означаючи ізоморфізм для ініціальних автоматів, вважають, що відображення γ переводить початковий стан одного автомата в початковий стан іншого автомата.

Уведене поняття має для автоматів той самий сенс, що й для графів. Як ізоморфні графи відрізняються один від одного тільки назвами своїх вершин, так ізоморфні автомати відрізняються лише іменами (назвами) своїх станів.

Розглянемо пару автоматів

A = (X, Y, U1, δ1, λ1) та B = (X, Y, U2, δ2, λ2),

які мають однакові вхідні й вихідні алфавіти. Отже, усі автоматні відображення, які індукують автомати A та B, мають однакові типи, тобто області визначення й області значень відображень збігаються. Це дає змогу ввести для автоматів такого типу деякі означення.

Стан ai U1 автомата A та стан bj U2 автомата B називають

невідрізнюваними, якщо для довільного слова p X* виконується рівність ϕAi(p) = ϕB j(p).

Наведене означення можна застосовувати й тоді, коли A = B. У цьому разі вводять відношення невідрізнюваності для різних станів того самого автомата A: стани ai, aj U1 автомата A називають

невідрізнюваними, якщо ϕAi(p) = ϕA j(p) для будь-якого p X*.

Автомати A та B називають невідрізнюваними, якщо для будь-якого стану a U1 автомата A існує невідрізнюваний стан b U2 автомата B і, навпаки, для будь-якого стану d U2 автомата B існує невідрізнюваний стан c U1 автомата A. Ініціальні автомати невідрізнювані, коли їхні початкові стани невідрізнювані.

Невідрізнюваність автоматів означає, що будь-яке автоматне відображення (поведінку), яке реалізує один з автоматів, може реалізувати інший автомат. Інакше кажучи, невідрізнювані автомати за зовнішньою поведінкою подібні між собою.

Неважко переконатися, що відношення невідрізнюваності H рефлексивне, симетричне і транзитивне, отже, є відношенням еквівалентності (на множині станів чи множині автоматів). У зв'язку з цим часто в літературі з теорії автоматів невідрізнюваність називають еквівалентністю, тобто використовують понят-

тя еквівалентні стани, еквівалентні автомати. Термінологічно це не зовсім зручно й не зовсім коректно, оскільки назву власти-

210