Лекції з теорії автоматів

ТАв_Ч1.doc (1 стор.)
ТАв_Ч2.doc (1 стор.)
Оригінал


В. Ф. Романов


Лекції з теорії автоматів


Частина 1

Теорія абстрактних автоматів




Володимир 2006


Навчальний посібник для студентів очної та заочної форм навчання спеціальностей
в області обчислювальної техніки, інформатики та управління.

ЗМІСТ



Частина 1. Теорія абстрактних автоматів ........................................................... 3

1.1. Загальні відомості .................................................................................. 3

1.2. Способи завдання автоматів .................................................................. 4

1.3. Приклади абстрактних автоматів, що виконують корисні дії ............... 6

1.4. Поведінка ізольованого синхронного автомата ...................................... 8

1.5. Регулярні вирази і кінцеві автомати ........................................... 10

1.6. Алгоритми і машини Тьюринга ............................................................. 11

1.7. Елементи теорії формальних граматик і мов .................................... 15

1.8. Умови автоматні відображення ........................................................ 20

1.9. Побудова графа автомата по входу-вихідним послідовностям ............ 21

1.10. Перетворення автоматів ................................................................... 22

Завдання і





ЧАСТИНА 1. ТЕОРІЯ абстрактного автомата



1.1. Загальні відомості

Абстрактний автомат (АА) - дискретний перетворювач інформації; являє собою безліч, що складається з шести елементів:

S = {X, Q, Y, δ, λ, q 1}

S - абстрактний автомат;

X - множина вхідних символів (вхідний алфавіт автомата):

X = {x 1,... , X m};

Q - безліч станів автомата:

Q = {q 1,... , Q n};

Y - безліч вихідних символів (вихідний алфавіт автомата):

Y = {y 1,... , Y p};

δ - Функція переходів автомата з одного стану в інший:

q j = δ (q i, x k),

де: q j - Наступне (нове) стан автомата; q i - Поточний стан автомата;
x k - Поточний вхідний символ;

λ - Функція виходів:

y l = λ (q i, x k);

q 1 - початковий стан автомата (застосовується також позначення q 0).

Автомат називається кінцевим, якщо множини X, Q, Y - кінцеві.





Рис.1. Подання абстрактного автомата


На рис. 1 t - дискретне час: t = nT, де T - Інтервал (такт), що розділяє дискретні моменти часу; якщо T = 1, то t = n, тобто дискретне час зіставляється впорядкованого ряду натуральних чисел.

Абстрактний автомат (АА) можна розглядати як "чорний ящик" з одним входом і одним виходом, з яким можна експериментувати, не знаючи, що знаходиться всередині.

Вихідний символ (y l Y) залежить не тільки від вхідного символу (x X), але і від
того, в якому стані (q i Q) знаходиться автомат. Автомат функціонує в дискретному часі; це означає, що елементи опису автомата задані тільки в згадані вище дискретні моменти.

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




Рис.2. Перетворення вхідних слів у вихідні


Сказане означає, що автомат може розглядатися як перетворювач вхідних слів у вихідні із збереженням довжини слів. Символи алфавітів, присутні на вході і виході автомата, будемо також називати вхідними і вихідними сигналами.

На практиці широке поширення одержали дві основні моделі, що описують функціонування АА:

1. Модель Мілі;

2. Модель Мура.


Модель Мілі.

Закони функціонування автомата Мілі представлені таким чином:

q (t +1) = δ (q (t), x (t))

y (t) = λ (q (t), x (t))

t - поточний момент часу;

t +1 - наступний момент часу;

q (t +1) - стан автомата в наступний момент часу;

q (t), x (t), y (t) - елементи опису автомата в поточний момент часу.


Модель Мура.

Закони функціонування автомата Мура представлені таким чином:

q (t +1) = δ (q (t), x (t))

y (t) = λ (q (t))

У моделі Мура вихідний сигнал явно залежить тільки від стану, а побічно -
і від вхідного сигналу.

Будь автомат можна спроектувати з тієї чи іншої моделі.


1.2. Способи завдання автоматів

Розглянь два основних способів завдання автоматів:

1. Табличний спосіб

Автомат Мілі

Для автомата Мілі табличний спосіб полягає в побудові двох таблиць: таблиці переходів (ТП) і таблиці виходів (ТБ).


x \ q


...

q i

...













x \ q


...

q i

...

.

.

.






















.

.

.










x k




 (q i, x k)
















x k




 (q i, x k)




.

.

.






















.

.

.










а б

Рис. 3. Табличний спосіб: а - таблиця переходів, б - таблиця виходів.

Приклад:

а) Таблиця переходів


x \ q


q 1

q 2

q 3

x 1

q 3

q 1

q 1

x 2

q 2

q 3

q 2


б) Таблиця виходів


x \ q


q 1

q 2

q 3

x 1

y 1

y 1

y 2

x 2

y 1

y 2

y 1

Автомат Мура


Таблиця переходів і таблиця виходів об'єднуються, і додається рядок
вихідних сигналів, відповідних станам автомата. На малюнку 4 показано таблиця переходів і виходів для автомата Мура.





...

 (q i, x k)

...

x \ q


...

q i

...

.

.

.










x k




 (q i, x k)




.

.

.











Рис. 4. Таблиця переходів і виходів

Приклад. Таблиця переходів і виходів:








y 1

y 1

y 3

y 2

y 3

x \ q

q 1

q 2

q 3

q 4

q 5

x 1

q 2

q 5

q 5

q 3

q 3

x 2

q 4

q 2

q 2

q 1

q 1


2. Графовая спосіб

Автомат представляється орієнтованим зв'язковим графом (Орграф), вершини якого відповідають станам автомата, а дуги - переходам із стану
в стан. Позначення вхідних та вихідних сигналів розподіляються в автоматах Мілі і Мура по-різному.

Побудуємо графи для автоматів Мілі і Мура за вищенаведеними таблицями:



Рис. 5. Подання автомата Мілі у вигляді графа




Рис. 6. Подання автомата Мура у вигляді графа


Зауваження: В автоматі Мілі вихідний сигнал виробляється при переході, а
в автоматі Мура присутня протягом усього періоду дискретного часу, поки
автомат знаходиться в даному стані.

Детермінований автомат - автомат, в якому є повна визначеність переходів з усіх станів у залежності від вхідних сигналів (під дією одного і того ж сигналу автомат не може переходити з будь-якого розглянутого стану в різні стани). Фрагмент графа, зображений на малюнку 7, не може ставитися до детермінованому автомату.




Рис.7. Фрагмент графа, що ілюструє невизначеність переходів


Зауваження: Недетермінірованние (наприклад, імовірнісні) автомати існують, але їх розгляд не передбачено в даному курсі.

Стан автомата q i називається стійким, якщо для будь-якого вхідного сигналу х до , Такого, що δ (q s , X k) = q i , Справедливе співвідношення: δ (q i , X k) = q i . (Тут q s - стан, що передує q i). Це означає, що, автомат не змінює свого стану при повторенні на наступному такті сигналу, що призвів його в стан q i . Фрагмент графа, що ілюструє стійкість стану, наведений на рисунку 8.




Рис. 8. Сталий стан автомата

Автомат називається асинхронним, якщо кожне його стан q i Q (i = 1, ..., n) стійко, в іншому випадку автомат називається синхронним. Синхронні автомати важливі для теорії, а на практиці частіше використовуються асинхронні; стійкість станів в асинхронних автоматах досягається введенням спеціальних сигналів синхронізації.


1.3. Приклади абстрактних автоматів, що виконують корисні дії


1. Автомат для затримки сигналу на один такт (для запам'ятовування на один такт)

Опишемо даний автомат таблицями і графом:


Таблиця переходів і таблиця виходів:


x \ q

q 0

q 1







x \ q

q 0

q 1

x 0

q 0

q 0







x 0

y 0

y 1

x 1

q 1

q 1







x 1

y 0

y 1



Оскільки автомат є двійковим, введемо позначення: x 0 = Y 0 = 0; x 1 = Y 1 = 1.




Рис. 9. Граф автомата для затримки сигналу на один такт


Простий аналіз показує, що вихідний сигнал в поточному такті повторює вхідний, який був на такт раніше.


2. Автомат для перевірки двійковій послідовності на парність.

Опишемо даний автомат таблицями і графом:


Таблиця переходів і таблиця виходів:


x \ q

q 0

q 1







x \ q

q 0

q 1

x 0

q 0

q 1







0

0

1

x 1

q 1

q 0







1

1

0





Рис. 10. Граф автомата для перевірки двійковій послідовності на парність


Аналіз показує, що «0» на виході автоматично виробляється при парному числі одиниць на вході, а «1» на виході виробляється при непарному числі одиниць на вході.

Обидва розглянутих автомата мають "слабку" пам'ять, але слабку в різному сенсі.
У першого автомата "коротка" пам'ять в часі (пам'ятає тільки один сигнал).
У другого автомата пам'ять "довга" (довжина вхідної послідовності може бути будь-який), але він розрізняє (розпізнає) лише два класи послідовностей.


3. Автомат для затримки сигналу на два такти.

Автомат має чотири стани, закодованих двома двійковими розрядами:
q 0 = 00; q 1 = 01; q 2 = 10; q 3 = 11.




Рис. 11. Граф автомата для затримки сигналу на два такти


Гідності застосованого кодування:


4. Двійковий послідовний суматор, реалізований для одного розряду вхідного коду.

Автомат має два стани: q 0 - немає переносу (додавання цифр операндів не вимагає обліку одиниці переносу з попереднього розряду коду);

q 1 - є перенос (одиниця переносу повинна бути врахована).




Рис. 12. Граф одноразрядного двійкового послідовного суматора


У чисельнику "дроби", записаної при кожній з дуг графа, вказані цифри доданків; в знаменнику - результат підсумовування в поточному розряді. Суматор дозволяє підсумовувати двійкові послідовності довільної довжини.

1.4. Поведінка ізольованого синхронного автомата

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

Приклади діаграм, що ілюструють поведінку даної автомата при різних початкових станах, наведені малюнку 13.







Рис.13. Поведінка ізольованого синхронного автомата


Відзначимо, що довжина циклу, виміряна числом дуг на діаграмі, не перевищує числа станів (n), те ж саме можна сказати і про "часу" входження в цикл, измеренном в умовних дискретних одиницях.

Проблема множення.

Теорема. Н ікакой кінцевий автомат не може перемножувати пари чисел
з довільно великим числом розрядів.

Причина полягає в тому, що зі зростанням числа розрядів співмножників при множенні необхідно накопичувати необмежено великі (за обсягом займаної
пам'яті) проміжні результати.

Для математичного доказу використовуємо метод "від протилежного": припустимо, що існує автомат S, Перемножуючий пари двійкових чисел з довільно великим числом розрядів (система числення може бути будь без обмеження спільності). Використовуємо для спростування останнього твердження окремий випадок: обидва співмножники дорівнюють 2 n. У цьому випадку кожен із співмножників містить одиницю, за якою слідують n нулів; результат множення (2 n  2 n = 2 2 n) містить одиницю
і 2 n нулів. Застосуємо економний спосіб використання пам'яті: пари розрядів співмножників подаються послідовно, починаючи з молодших розрядів (аналогічно тому, як це робилося в розглянутому вище суматорі).

Щоб автомат правильно працював, він повинен після припинення подачі співмножників додати до вже виробленим n + 1 нулях ще n - 1 нулів, а потім на закінчення одиницю. Але після припинення подачі співмножників автомат буде працювати як ізольований.

Якщо ізольований автомат S має k станів і здатний виробити на виході поспіль n нулів, де nk, то це означає, що він знаходиться в поглинає стані або увійшов у цикл. Отже, він уже не зможе виробити одиницю. Так як завжди можливо зробити значення n таким, що n - 1  k, правильний результат при виконанні зазначеного нерівності не буде отриманий і, отже, припущення про існування автомата S приводить до суперечності. Теорема доведена.


1.5. Регулярні вирази і кінцеві автомати


Розглянемо структуру рекурсивних визначень, які застосовуються як засіб суворого математичного опису класів об'єктів. Рекурсивне визначення деякого класу K включають наступні частини:

База - визначає один або кілька найпростіших об'єктів класу До.

Рекурсія - складається з одного чи декількох пунктів. У кожному пункті говориться, що якщо певні види об'єктів належать класу К, то й інші об'єкти, побудовані з перших по деякому правилу, також належать класу До. Число пунктів рекурсії відповідає числу правил.

Обмеження - встановлює, що ніякі об'єкти, крім тих, які побудовані за допомогою застосування бази та рекурсії, не належать класу До.

Приклад: рекурсивне визначення правильного скобочной вирази (ПСВ).

БАЗА: () - ПСВ;

Рекурсія:

а) якщо А - ПСВ і В - ПСВ, то АВ - ПСВ;

б) якщо А - ПСВ, то (А) - ПСВ;

ОБМЕЖЕННЯ: ніяких інших ПСВ немає.

Відзначимо, що у визначенні використані метасимволи А і В, що позначають
будь ПСВ; вираз АВ позначає конкатенацію (послідовну запис)
А та В.

Існує тісний зв'язок між можливостями кінцевих автоматів і тими вхідними послідовностями, які автомат розпізнає. Будемо говорити, що автомат S розпізнає послідовність вхідних сигналів, якщо ця послідовність призводить до того, що автомат переходить в заздалегідь обумовлений стан або видає обумовлений вихідний сигнал. Можна побудувати автомат, що розпізнає, наприклад, слова деякої мови, тобто відрізняє "правильне" вхідне слово від неприпустимого в даній мові вхідного слова.

Визначимо рекурсивно клас R регулярних виразів на заданому алфавіті .

БАЗА: Будь однобуквеному символ x   - регулярний вираз (xR ).

Рекурсія:

а) якщо E - регулярний вираз і F - регулярний вираз, то E F
(Вибір) - регулярний вираз ((E F)R );

б) якщо E - регулярний вираз і F - регулярний вираз, то EF - регулярний вираз (EFR );

в) якщо E - регулярний вираз, то і E * - регулярний вираз (E *R ).

ОБМЕЖЕННЯ: ніяких інших ПСВ немає.

У наведеному визначенні E і F - Метасимволи, що позначають будь-які регулярні вирази; E * - будь-яке число повторень E, включаючи і відсутність E. Пріоритет введених операцій зростає в порядку їх перерахування.

Теорема Кліні:

1. До онечний автомат може розпізнавати лише регулярні безлічі послідовностей.

2. Будь регулярне безліч послідовностей може бути розпізнано 1 деяким кінцевим автоматом.

Доказ теореми наведено в [1].

Принципова важливість теореми Кліні полягає в тому, що вона встановлює обмеження на можливості кінцевих автоматів; в теорії алгоритмів доведено, що будь-яке обчислення може бути зведене до розпізнавання.


1.6. Алгоритми і машини Тьюринга

У даному розділі розглядаються більш потужні (у порівнянні з кінцевими автоматами) моделі пристроїв, що виконують обчислення, - машини Тьюринга (МТ). Аналіз показав, що за допомогою машин Тьюринга можна реалізувати будь-який алгоритм. Одночасно МТ служить для уточнення самого поняття алгоритму та його формалізації, оскільки, як встановлено в теорії обчислень, широко вживані словесні визначення алгоритму не є точними і вичерпними.

Розглянемо, наприклад, таке визначення [2]: Алгоритм - це певне на деякій мові кінцеве припис (спосіб, рецепт), що задає дискретну
послідовність здійснимих елементарних операцій для вирішення проблеми. Процес виконання припису складається з окремих кроків, на кожному з яких виконується одна чергова операція.

Як зазначено в [2], це визначення, ясна в інтуїтивному сенсі, не є формальним. Спожиті в ньому терміни "припис", "елементарна операція", а також об'єкти, до яких застосовується алгоритм, вимагають уточнення, якщо ми хочемо говорити про алгоритми суворо. Алгоритми в інтуїтивному сенсі не є математичними об'єктами, до них не застосовні формальні дослідження і докази. Так, порівняння двох алгоритмів по ефективності, перевірка їх еквівалентності і т. д., можливі тільки на основі їх формального представлення.

Машина Тьюринга являє собою нескінченний автомат, завдяки нескінченній (потенційно) стрічці, розбитою на осередки. В осередках записуються символи деякого алфавіту МТ. Є також кінцевий автомат з головкою запису і зчитування (ГЗЧ). ГЗЧ оглядає одну комірку стрічки в поточний момент дискретного часу.





Рис.14. Машина Тьюринга


Функції ГЗЧ: зчитування символу з оглядається осередку; запис символу
в оглядається клітинку; пересування вліво або вправо на одну клітинку.

У кожен момент часу МТ описується наступною п'ятіркою:

(Q i, s j, δ (q i, s j), λ (q i, s j), d (q i, s j)),

де

q i - стан МТ в поточний момент часу;

s j - оглядає, символ в поточний момент часу;

δ - Функція переходів, яка визначає наступний стан;

λ - функція виходів, визначальна запис нового символу в оглядається
осередок;

d - Функція, що визначає пересування голівки вліво (L) або вправо (R)
на один крок.

Більш коротке позначення елементів п'ятірки: (q i , S j , Q ij , S ij , D ij).

Теза Тьюринга: Л Юбою процес, який було б природно назвати
ефективною процедурою 2, може бути реалізований МТ.

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

Приклади машин Тьюринга для конкретних обчислень.


1. Лічильник парності одиниць.





Рис.15. МТ для лічильника парності


На рис. 15 показана МТ в початковому стані q 0, при цьому оглядається перший символ двійкової послідовності, яка закінчується обмежувачем B. Далі на кожному такті ГЗЧ просувається вправо, замінюючи всі символи символом "0", причому зміна
станів (q 0 на q 1 і назад) відбувається всякий раз, коли ГЗЧ виявить одиницю. Таким чином, стан q 0 пов'язано з парним числом виявлених одиниць, а стан q 1 - з непарним. Останов МТ (перехід в заключне стан H ) Відбувається після досягнення символу B, при цьому на його місце записується "0", якщо число одиниць
у вихідній послідовності було парних, і "1", якщо це число було непарним.
Після завершення процесу обчислень ГЗЧ буде вказувати на цю комірку з заключній інформацією, а у всіх інших осередках стрічки будуть записані нулі.

Уявімо роботу МТ двома способами: таблицею і графом.

Рядки таблиці містять всі "п'ятірки", що описують функціонування МТ.

Таблиця


q i

s j

q ij

s ij

d ij

q 0

0

q 0

0

R

q 0

1

q 1

0

R

q 0

В

Н

0

-

q 1

0

q 1

0

R

q 1

1

q 0

0

R

q 1

В

Н

1

-






Рис. 16. Граф лічильника парності одиниць


У вершинах графа явно вказаний символ, що позначає рух ГЗЧ вправо в кожному з двох станів. Заключне стан позначено на малюнку буквою H - "Halt" (останов).


2. Машина Тьюринга для перевірки правильності скобочной виразів.

Рекурсивне визначення правильного скобочной вирази (ПСВ) було дано
в розділі 1.3. Зауважимо, що кінцевий автомат не може вирішити поставлене завдання для скобочной вирази довільної довжини. МТ вирішує задачу в загальному випадку, так як наявність необмеженої стрічки еквівалентно необмеженому обсязі пам'яті.





Рис. 17. МТ для перевірки скобочной виразів


Скобочной вираз укладено між лівим і правим обмежувачами, позначеними символом А. У початковому стані автомата ГЗЧ оглядає перший символ скобочной вирази (рис. 17). Реалізація обчислень представлена ​​графом (рис. 18).





Рис. 18. Граф МТ для перевірки скобочной виразів


Робота машини: спочатку ГЗЧ рухається вправо до першої правої дужки, замінює її символом X, переходить в стан q 1 і рухається вліво до найближчої лівої дужки, замінює її символом X, переходить в стан q 0, і човниковий рух повторюється.

Якщо машина, перебуваючи в стані q 1, досягає лівого символу А, то друкує "0" і зупиняється - скобочной вираз неправильно.

Якщо машина, перебуваючи в стані q 0, досягає правого символу А, не виявивши більше правої дужки, то переходить в заключне стан q 2, пов'язане з рухом вліво, і в останній раз переглядає послідовність: чи не залишилася непарна ліва дужка. Якщо по шляху зустрінеться ліва дужка, то машина друкує "0" і зупиняється. При досягненні в стані q 2 лівого символу А, машина друкує "1" і зупиняється - скобочной вираз правильно.


3. Машина Тьюринга для множення двох чисел в унарні коді.

Дія машини представлено малюнками 19 - 21.



Рис. 19. МТ для множення - початковий стан


Рис. 20. МТ для множення - результат операції





Рис. 21. Граф МТ - розмножувального пристрою


На рис. 21 граф представлений у скороченому вигляді - не показані петлі з однаковими чисельником і знаменником.

МТ являє собою простий базис для опису ефективних процедур,
оскільки всі кроки, що регламентують поведінку автомата, визначаються чіткими правилами. У сучасній термінології, МТ - простий базис для опису алгоритмів і уточнення самого поняття алгоритму.

У наведених вище прикладах для кожного обчислення використовувався свій спеціальний кінцевий автомат - так звана конкретна машина Тьюрінга. Кінцевий автомат в конкретних МТ грає роль алгоритму обчислень.

Можна вважати, що будь-яка МТ обчислює деяку функцію (заключне вміст стрічки) від заданого аргументу (початковий вміст стрічки). У зв'язку
з цим виникло поняття: функція, обчислювана за Тьюрингу.

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

УМТ має структуру, показану на рис. 22.



Рис. 22. Структура УМТ

Ліва частина стрічки (до символу q i) імітує стрічку конкретної МТ, права - містить опис автомата конкретної МТ у вигляді п'ятірок.

Символ М показує розташування ГЗЧ конкретної МТ; будемо вважати, що оглядає, символ знаходиться праворуч від символу М.

Пара осередків q i, s j - зона режиму, яка вказує поточний стан і поточний оглядає символ (на малюнку це символ "0").

Робота УМТ: УМТ починає роботу з запам'ятовування символів q i, s j зони режиму, потім ГЗЧ рухається вправо до тих пір, поки не знайде п'ятірку, в якій перші два символи збігаються з символами зони режиму. Знайшовши таку п'ятірку, УМТ запам'ятовує q ij, s ij, d ij, і ГЗЧ рухається вліво. Далі виконуються наступні дії:

  1. q i: = q ij , Тобто в зону режиму записується символ, що позначає новий стан автомата конкретної МТ;

  2. праворуч від М записується s ij;

  3. виконується зсув М згідно значенню d ij (L або R), що відповідає пересуванню ГЗЧ імітованої машини;

  4. запам'ятовується новий оглядає символ (праворуч від М) і переноситься
    в зону режиму в якості s j.


Таким чином, зона режиму виявляється оновленої, і зазначені дії повторюються до останову машини.

Варіант формулювання тези Тьюринга: У ичісліми ті, і лише ті, об'єкти, які можуть бути обчислені УМТ.

Згідно Тьюрингу, алгоритмом можна вважати тільки ту процедуру, закодовану для МТ, яка призводить до останову машини.

У зв'язку з цим виникає питання: чи існує універсальний распознаватель алгоритмів, тобто МТ, яка для будь-якої іншої МТ визначить, зупиниться остання чи ні. Це питання названий в теорії машин Тьюринга проблемою зупину. Доведено, що проблема останову нерозв'язна і, отже, універсального распознавателя алгоритмів не існує [1]. Існують і інші алгоритмічно нерозв'язні проблеми, до доказу нерозв'язності яких залучається механізм обчислень, введений Тьюрінгом.

Прості системи (базиси) для вирішення проблем вичіслімості створили незалежно один від одного і інші видатні дослідники в області теорії алгоритмів: А. Черч (математичний апарат рекурсивних функцій), А. А. Марков (нормальні алгорифм, що зводяться до перетворення слів у деякому алфавіті) , Е. Пост (механізм перетворення двійкових послідовностей, подібний МТ). Всі названі системи рівноцінні з точки зору їх принципових можливостей і еквівалентні як формалізми для визначення алгоритму [3].


1.7. Елементи теорії формальних граматик і мов
Основні визначення

Алфавіт - безліч символів, наприклад,  = {a, b, c, ..., z}.

Ланцюжок (слово) - послідовність символів з ​​алфавіту. Для позначення ланцюжків використовуються малі літери латинського алфавіту: α, β, γ ..., а самі ланцюжка укладаються в ординарні лапки. Наприклад,  = {a, b, c, =, -, +} - алфавіт,
α = 'a + b = c'-ланцюжок над алфавітом; п устая ланцюжок ε =' '- ланцюжок, що не містить символів.

Рекурсивне визначення ланцюжка над алфавітом :

БАЗА : Ε - ланцюжок;

Рекурсія: якщо x   і А - ланцюжок, то Ах - ланцюжок (тут A - метасимвол, що позначає будь-яку ланцюжок);

ОБМЕЖЕННЯ: інших ланцюжків немає.

Довжина ланцюжка - число символів у ланцюжку, полягає в прямі дужки, наприклад, | α | = 5, | ε | = 0.

Подцепочка: ланцюжок β є подцепочкой ланцюжка α, якщо існують такі ланцюжки γ і δ, бути може, порожні, що α = γ β δ.

Ланцюжок 'перемога' містить подцепочкі: 'обід', 'біда', 'їжа', 'да' (тут ланцюжка задані над алфавітом російської мови).

Конкатенація - зчеплення ланцюжків; позначається αβ або α · β. Конкатенація асоціативна, але не коммутативна.

Позначимо через  * - множина всіх ланцюжків над алфавітом .

Система { *, ·} утворюють відому алгебру - напівгруп, в якій  * - носій алгебри, · - асоціативна бінарна операція.

Звернення ланцюжка. Ланцюжок β називається зворотної ланцюжком ланцюжка α, якщо вона являє собою послідовність символів ланцюжка α, виписаних в зворотному порядку.


Формальна мова

Формальним мовою L на алфавіті  називається будь-яке підмножина безлічі  * (L  *).

Приклади:

1) деякі мови програмування, наприклад, АЛГОЛ (з низкою застережень);

2)  = {0, 1}, L = {α |, | α | 100} - множина ланцюжків в двійковому алфавіті, довжина яких не перевищує 100 символів;

3) L = {ε} - порожній мову;

4) L =  *;

5)  = {a, b, c}, α = {a n b n c n | n 1}, тут умовний показник n при символі - число повторень символу.

Операції над мовами. Оскільки мови - множини, до них застосовні відомі теоретико-множинні операції, зокрема, об'єднання мов (L 1  L 2) і перетин мов (L 1  L 2).

Специфічна операція - до онкатенація мовами:

Нехай L 1 - мову на  1 і L 2 - мову на  2, тоді конкатенація мов має вигляд:

L 1 · L 2 = {α β | α  L 1, β  L 2}


Способи завдання мов:

1. Спосіб перерахування елементів; в штучних мовах не завжди зручний
через можливе великого числа елементів.

2. Спосіб завдання за допомогою характеристичного властивості:

L = {α | Р (α)}, де Р (α) - предикат (характеристичне властивість безлічі).

Спосіб завдання мови не повинен обмежувати довжину елемента, що входить в мову. У теорії формальних граматик відомі методи визначення мов, вільні від зазначеного обмеження. Виділимо два найбільш важливих методу.

  1. Завдання мов допомогою допускають (розпізнаючих) автоматів.

  2. Завдання мов за допомогою граматик, що породжують.

Розпізнає автомат виділяє з ланцюжків (слів), що подаються на його вхід, слова, що належать обумовленому мови.


Розпізнає

автомат

вхідна слово да (немає)




Породжує граматика генерує "правильні" ланцюжки, що належать мові L.


Генерування ланцюжків мови


Породжує

граматика



Далі предметом нашого розгляду будуть породжують граматики.

Компонентами граматик, що породжують є:

  1. Два алфавіту:

- Допоміжний (нетермінальний);

- Основний (термінальний).

Ці два алфавіту не містять загальних символів, їх перетин порожньо.

  1. Безліч правил виводу (продукций), що складається з впорядкованих пар ланцюжків  α, β . Кожна ланцюжок в цих парах складена з об'єднання елементів термінального та нетермінального алфавітів. Сама продукція позначається α -> β і має на увазі заміну при відповідних умовах ланцюжка α ланцюжком β.

  2. Початковий символ (аксіома) граматики - один з нетерміналів, який наділений особливим статусом - з нього починається породження мови.

Приймемо угода, що стосується позначень у формальних граматиках:

Породжують граматики загального типу (ПГОТ)

Позначення граматики: G =  N, , P, S ,

де:

N - нетермінальний алфавіт;

 - термінальний алфавіт;

P - множина продукцій; тобто правил виводу виду  -> β, де α, β  (N  ) *;

S - аксіома граматики.


Приклад 1. G 1 =  {S}, {a, b}, P, S ,

де:

P: 1. aSa -> aSb;

2. S -> a;

3. S -> aSa.

Безпосередня виводимість: ланцюжок β безпосередньо виведена з ланцюжка α в граматиці G, якщо знайдуться такі ланцюжки γ 1, γ 2,1,2, що α = γ 11 γ 2,
β = γ 12 γ 2, і серед правил виводу мається правило ω 1 -> ω 2.

У ланцюжку α подцепочкі γ 1, γ 2 - контекст. Безпосередньо виведена ланцюжок виходить застосуванням однієї продукції граматики; позначення безпосередньої виводимості: α ==> β. Приклади безпосередній виводимості у наведеній граматиці: aSa ==> aSb; aSa ==> aaa.

Знак «==>» можна інтерпретувати як позначення бінарного відносини безпосередньої виводимості.

Використовуючи поняття безпосередньої виводимості, визначимо виводимість.
Будемо записувати: α ==> * β (β виведена з α), якщо існує послідовність
ланцюжків α 0, α 1, α 2,..., α n, таких, що α 0 = α, α n = β і α i ==> α i +1 (i = 0, ..., i -1), або
 = . Вказану послідовність ланцюжків назвемо висновком довжини n.

Таким чином, виводимість - рефлексивне і транзитивне бінарне відношення.

У розглянутій граматиці G 1 можливі висновки: S ==> * a (висновок довжини 1);
S ==> * aaa (висновок довжини 2: S ==> * aSa ==> * aaa).

Мова, породжуваний граматикою (позначення - L (G)) - безліч термінальних ланцюжків, що виводяться з аксіоми, тобто L (G) = {z ε Σ * | S ==> * z}.

Приклад 2. G 2 = <N, Σ, P, S>;

N = {A, B, C, S}; S - аксіома;

Σ = {a, b, c};

P: 1. S -> aSBC;

2. S -> abC

3. CB -> BC

4. bB -> bb

5. bC -> bc

6. cC -> cc

Приклад виведення: S ==> aSBC ==> aabCBC ==> aabBCC ==> aabbCC ==>
==> AabbcC ==> aabbcc (тут правила застосовані в порядку нумерації).

Граматика G 2 породжує мову L (G) = {a n b n c n | N  1}.

Породжують граматики загального типу реалізуються машинами Тьюрінга.

У теорії і практиці розробки систем програмування, операційних систем, засобів синтаксичного аналізу, компіляції та перекладу застосовуються й інші
граматики, наприклад, НС-граматики (граматики безпосередньо складових),
КС-граматики (контекстно-вільні граматики), А-граматики (автоматні граматики).

Всі відомі граматики є окремим випадком ПГОТ і виходять за допомогою обмежень, що накладаються на продукції.

Автоматні граматики

Породжує граматика G =  N, , P, S  називається автоматної, якщо її правило виведення має наступний вигляд:

- Правосторонні правила, або - Лівосторонні правила,

де A, B - елементи нетермінального алфавіту; a - елемент термінального алфавіту.

Мови, породжувані А-граматиками, називаються регулярними мовами (також мовами Кліні).

Приклад 3: G 3 =  {S, A}, {a, b}, P, S> , де прийняті правосторонні правила:

P: 1. S -> aS;

2. S -> aA;

3. A -> bA;

4. A -> b.

Приклад виведення: S = => AS = => AaA = => AabA = => Aabb. У загальному випадку граматика G 3 породжує мову L (G 3) = {a n b m | N, m> 0}.

А-граматики малопотужні (цей термін характеризує велика в середньому число
кроків при виведенні). Тим не менш, існує нескладне доказ того факту, що А-граматики породжують всі можливі кінцеві мови.


Ілюстрація зв'язку між автоматними граматиками і автоматами

Розглянемо правосторонню А-граматику G 4 =  N, , P, S :

N = {S 1, S 2, S 3}, де S 1 - аксіома; Σ = {x, y, a, b}

P: 1. S 1 -> ybS 1

2. S 1 -> xaS 2

3. S 2 -> xaS 2

4. S 2 -> yaS 3

5. S 3 -> xbS 1

Правила виведення включають вхідні термінальні символи x і y і вихідні термінальні символи а й b.

Граф автомата Мілі, який реалізує дану граматику, наведено на рис. 23.





Рис. 23. Граф, який реалізує граматику G 4


Малюнок ілюструє наступні відповідності:

Отриманий автомат є перетворювачем вхідних слів у вихідні. Так, слово 'yxyx' перетвориться в слово 'baab'. Безліч вихідних слів утворює мову, який породжується даною граматикою.

Взаємодія автомата із середовищем

В теорії автоматів значне місце займали експериментальні методи:
дослідження "поведінки" автоматів на моделях, що відображають взаємодію автоматів з різними видами зовнішнього середовища, що має дискретне, зокрема, автоматні опис.



Автомат А


Середа Е




x (t) x (t) y (t) y (t)

Середовище Е можна розглядати як детермінований або стохастичний автомат, поведінка якого залежить від його внутрішнього стану, зовнішніх сигналів і часу.

Введемо наступні позначення:

y (t) - дії автомата;

х (t) - реакція середовища;

х (t) = +1 - сприятлива реакція (виграш);

х (t) = -1 - несприятлива реакція (програш).

У стаціонарній середовищі кожна дія автомата викликає з імовірністю p m значення реакції х (t) = -1 і з імовірністю q m значення х (t) = +1. При цьому, q m = 1 - p m;
b m = q m - p m - оцінка математичного очікування виграшу за дію y m .

Прийнято вважати, що автомат має доцільним поведінкою, якщо на безлічі експериментальних результатів (при різних співвідношеннях параметрів q m і p m) математичне сподівання виграшу М> М 0, де М 0 - математичне очікування виграшу при q m = p m = 0,5.

Історично склалися такі напрямки досліджень із застосуванням моделювання:

Поведінка автоматів в детермінованих і випадкових середовищах.

Ігри автоматів.

Колективну поведінку автоматів.

Клітинні автомати.

Велику роль у розвитку фундаментальної теорії автоматів зіграли такі дослідники, як Дж.фон Нейман, К. Шеннон, М. Л. Цетлін, В. М. Глушков, М. Мінський.

Підходящим керівництвом для початкового вивчення теорії формальних граматик є книга М. Гросса і А. Ланта [4].

1.8. Умови автоматні відображення

Як уже зазначалося, автомат може розглядатися як перетворювач слів
в алфавітах; проте не всяке перетворення слів може бути реалізовано автоматом. Іншими словами, не всяке відображення вхідних слів у вихідні є
автоматним.

Умови автоматні відображення:

1. Відображення має бути однозначним: кожному вхідному слову зіставляється єдине вихідна слово.

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

3. Відображення повинне зберігати довжину слова (кожне вхідне слово відображається в вихідну слово тієї ж довжини).

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

Умови автоматні накладають жорсткі обмеження на клас відображень, реалізованих автоматом. На практиці більшість відображень не задовольняють
умовам автоматних. Однак існує стандартний прийом, який дозволяє перетворити будь алфавітне відображення в автоматних. При цьому використовуються дві операції:

ε - приписується один раз або багаторазово до кінця вхідних слів,

δ - приписується один раз або багаторазово до початку вихідних слів.

У послідовній процедурі вирівнювання на кожному кроці додається
не більше ніж по одній букві ε і δ, з наступною операцією поповнення.

Приклад: Перевіримо автоматні відображення:

000 -> 001

001 -> 011

Рішення:

0 -> 0

00 -> 00

00 -> 01

З двох останніх рядків випливає, що відображення не однозначно.

Додамо по одній порожній букві до вхідних і вихідних словами:

000ε -> δ001

001ε -> δ011

Перевіримо виконання однозначності:

0 -> δ

00 -> δ0

00 -> δ00

001 -> δ01

Неоднозначність усунена - відображення задовольняє умовам автоматних.
У даному прикладі ми застосували послідовну процедуру приведення відображення до автоматні, при цьому виявилося достатнім одноразове приписування порожніх букв до вхідних і вихідних словами.

Існує стандартна процедура вирівнювання: до вхідного слову приписується стільки букв ε, яка довжина вихідного слова, і, відповідно, до вихідного слову приписується стільки букв δ, яка довжина вхідного слова. Стосовно до розглянутого прикладу автоматні відображення буде у цьому випадку наступним:

000    ->    001

001    ->    011.


1.9. Побудова графа автомата по входу-вихідним послідовностям

Проектування автомата в ряді випадків може починатися з загального або частково деталізованого представлення про його дію. Зокрема, спочатку алгоритм функціонування автомата може бути представлений словесним описом, тимчасовими діаграмами або вхід-вихідними послідовностями (перерахуванням пар слів, що відображають залежність вихідних слів від вхідних). Розглянемо докладніше останній випадок.

Нехай дано відображення:

000 -> 000

001 -> 001

010 -> 010

011 -> 011

100 -> 110

101 -> 111.

Попередній етап побудови графа автомата полягає в перевірці умов автоматні відображення. Легко бачити, що в даному випадку ці умови виконані.

Основний етап складається з наступних кроків.

1. Побудуємо граф у вигляді "орієнтованого" дерева (рис.24); q 0 - позначення початкової вершини, з якої починається побудова.





Рис. 24. Граф, представлений у вигляді дерева


2. Виділимо і об'єднаємо однакові піддерев шляхом склеювання вершин третього ярусу (рис. 25).





Рис. 25. Граф після склеювання вершин


4. Об'єднаємо (шляхом склеювання) вершини останнього ярусу з початковою вершиною і введемо ідентифікатори станів.

У результаті отриманий граф автомата Мілі, який реалізує заданий відображення (рис. 26).




Рис. 26. Граф автомата Мілі, який реалізує заданий відображення


1.10. Перетворення автоматів

Два автомата називаються еквівалентними, якщо вони реалізують однакові відображення вхідних слів у вихідні на всій області визначення відображення. Автомати Мілі та Мура можуть бути перетворені одна в одну, тобто для всякого автомата Мура може бути побудований еквівалентний йому автомат Мілі і, навпаки, для всякого автомата Мілі - еквівалентний йому автомат Мура.

1. Перетворення автомата Мура в автомат Мілі.

Нехай S А - вихідний автомат Мура; S B - автомат Мілі, який є метою перетворення. Автомат Мура характеризується шестіелементной безліччю:

S А = (X A, Q A, Y A, δ A, λ A, q 1A)

Побудуємо автомат Мілі: S B = (X B, Q B, Y B, δ B, λ B, q 1B).

Чотири перші компоненти автомата Мілі, а також початковий стан визначаються виходячи з рівностей:

X B = X A,

Q B = Q A,

Y B = Y A,

δ B = δ A,

q 1 B = q 1 A.


Різниця полягає у функціях виходів. Вони визначаються так: якщо в автоматі Мура δ A (q i, x j) = q s і y k = λ A (q s), то в автоматі Мілі λ B (q i, x j) = y k (Рис. 27).




Рис. 27. Фрагмент перетворення автомата Мура в автомат Мілі

У загальному випадку, якщо у вершину q s входять декілька дуг, то вихідний сигнал y k, записаний у вершині q s, переноситься в позначення всіх дуг, що входять в дану вершину.

2. Перетворення автомата Мілі в автомат Мура

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

S A = (X A, Q A, Y A, δ A, λ A, q 1 A) - вихідний автомат Мілі;

S B = (X B, Q B, Y B, δ B, λ B, q 1 B) - цільовий автомат Мура.

Для алфавітів автомата S B будуть справедливі такі рівності:

X B = X A,

Y B = Y A.

Для визначення безлічі Q B кожному станом q s  Q A поставимо у відповідність безліч Q s всіляких пар виду (q s, y t), де y t - вихідний сигнал, приписаний дузі, що входить до q s. (фрагмент графа зображений на рис. 28).



Рис. 28. Вершина q s з вхідними дугами

У цьому випадку Q s являє собою безліч пар виду:

Q s = {(q s, y l), (q s, y 2), (q s, y 3)}

У загальному вигляді, якщо D - множина дуг, що входять у вершину q s , То Q s визначається наступним чином:

Q s = {(q s, y t) | y t  D}

Отже, число елементів Q s дорівнює числу різних вихідних сигналів при дугах
автомата S A, що входять в стан q s . Безліч станів автомата S B отримаємо як теоретико-множинне об'єднання множин Q s, асоційованих з усіма станами q s вихідного автомата.

Висновок: число станів в автоматі Мура в середньому більше, ніж число станів в автоматі Мілі.

Функція λ B визначається так: кожному стану автомата S B, який представляє собою пару (q s, y t), ставиться відповідність вихідний сигнал y t .

Функція δ B визначається наступним чином: якщо в автоматі Мілі S A є перехід δ A (q i, x j) = q s і при цьому видається вихідний сигнал λ A (q i, x j) = y p, то в автоматі Мура S B буде перехід з безлічі Q i станів, породжених станом q i , В стан (q s, y p) під впливом вхідного сигналу x j (Рис. 29).




Рис. 29. Перетворення автомата Мілі в автомат Мура

В якості початкового стану q 1 B можна взяти будь-який стан з безлічі Q 1, породженого станом q 1 A.

ЗАВДАННЯ І ВПРАВИ


1. Дати рекурсивне визначення ланцюжка над деякими алфавітом, використовуючи поняття порожній ланцюжка і конкатенації.

2. На вхід кінцевого автомата подається послідовність з нулів та одиниць. Зобразити граф, що описує поведінку розпізнає автомата, і записати регулярний вираз для розпізнаваної послідовності для випадків:

а) число одиниць ділиться на 3;

б) всі одиниці з'являються серіями не менше ніж з трьох одиниць;

в) одиниця не з'являється в момент часу, що ділиться на 2 або 3.

3. Замінити регулярний вираз (a  b) * таким, в якому не використовується
знак "".

4. Чи збігаються безлічі послідовностей, що подаються регулярними виразами

а) b (ab  b) * a і bb * a (bb * a) *;

б) (a * ab  ba) * a * і (a  ab  ba) *?

5. Які з наступних рівностей вірні:

а) E * F = (E  E *) * F;

б) E * F * = (E  F) * (EF) *;

в) E * F * = E * EF *  E * FF *;

г) E (FGE) * FG = EF (GEF) * G?

Тут E, F, G - метасимволи, що позначають певні послідовності символів алфавіту.

6. Які з наступних множин послідовностей можуть бути розпізнані кінцевим автоматом:

а) безліч всіх послідовностей: 0, 1, 00, 01, 10, 11, 000, 001, 010, ...;

б) числа 1, 2, 4, 8, ..., 2 n,..., записані в двійковій системі числення;

в) те ж саме безліч чисел, записаних в унарні коді: 1, 11, 1111, 11111111,
1111111111111111, ...;

г) безліч послідовностей, в яких число нулів дорівнює числу одиниць;

д) послідовності: 0, 101, 11011, ..., 1 k 01 k (k - число повторень одиниці)?


Література

  1. Мінський М. Обчислення й автомати. - М.: Мир, 1971. - 364 с.

  2. Карпов Ю. Г. Теорія автоматів. - СПб.: Питер, 2002. - 206 с.

  3. Кузнецов О. П., Адельсон-Бєльський Г. М. Дискретна математика для інженера. - М.: Енергія, 1986. - 336 с.

  4. Гросс М., Лант А. Теорія формальних граматик. - М.: Мир, 1971. - 290 с.

  5. Горбатов В. А. Основи дискретної математики. - М.: Вищ. школа, 1984. - 310 с.



Романов Володимир Федорович

При написанні цього навчального посібника використовувалися конспекти лекцій
автора, підготовлені студентами Власенко В. В., Володимирової Н. В.


1 Інакше кажучи, представимо.

2 Алгоритмом в сучасній термінології
Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації