Курсова робота № 1
Моделювання роботи кінцевого распознавателя
Навчальна мета. Отримання практичних навичок побудови моделей кінцевих розпізнавачів.
Теоретичні відомості.
недетермінірованного кінцевий автомат (НКА) - це п'ятірка M=(Q, T, D, q0, F), де - кінцеве безліч станів;- Кінцеве безліч допустимих вхідних символів (вхідний алфавіт);
D - функція переходів (відображає безліч Q? (T {e}) в безліч підмножин множини Q), що визначає поведінку керуючого пристрою; Q - початковий стан керуючого пристрою; Q - безліч заключних станів.
Робота кінцевого автомата являє собою деяку послідовність кроків, або тактів. Такт визначається поточним станом керуючого пристрою і вхідним символом, розглядаємим в даний момент вхідний головкою. Сам крок складається з зміни стану і, можливо, зсуву вхідної головки на одну клітинку вправо (рис. 9.2).
Рис. 9.2:
Недетермінізм автомата полягає в тому, що, по-перше, перебуваючи в деякому стані і оглядаючи поточний символ, автомат може перейти в одне з, взагалі кажучи, декількох можливих станів, і по-друге, автомат може робити переходи по e.
Нехай M=(Q, T, D, q0, F) - НКА. Конфігурацією автомата M називається пара (q, w) Q? T *, де q - поточний стан керуючого пристрою, а w - ланцюжок символів на вхідних стрічці, що складається з символу під головкою і всіх символів праворуч від нього. Конфігурація (q0, w) називається початковою, а конфігурація (q, e), де q F - заключної (або допускає).
Нехай M=(Q, T, D, q0, F) - НКА. Тактом автомата M називається бінарне відношення, визначене на конфігураціях M таким чином: якщо p D (q, a), де a T {e}, то (q, aw) (p, w) для всіх w T *.
Будемо позначати символом + (*) Транзитивне (рефлексивно-транзитивне) замикання відносини.
Кажуть, що автомат M допускає ланцюжок w, якщо (q0, w) * (q, e) для деякого q F. Мовою, що допускаються (розпізнаваним, обумовлених) автоматом M, (позначається L (M)), називається безліч вхідних ланцюжків, що допускаються автоматом M. Тобто
Важливим окремим випадком недетермінірованного кінцевого автомата є детермінований кінцевий автомат, який на кожному такті роботи має можливість перейти не більше ніж в один стан і не може робити переходи по e.
Нехай M=(Q, T, D, q0, F) - НКА. Будемо називати M детермінованим кінцевим автоматом (ДКА), якщо виконані такі дві умови: (q, e)=для будь-якого q Q, і (q, a) містить не більше одного елемента для будь-яких q Q і a T.
Так як функція переходів ДКА містить не більше одного елемента для будь-якої пари аргументів, для ДКА ми будемо користуватися записом D (q, a)=p замість D (q, a)={p}.
Кінцевий автомат може бути зображений графічно у вигляді діаграми, що представляє собою орієнтований граф, в якому кожному станом відповідає вершина, а дуга, позначена символом a T {e}, з'єднує дві вершини p та q, якщо p D (q, a ). На діаграмі виділяються початкова й заключні стани (у прикладах нижче, відповідно, входить стрілкою і подвійним контуром).
Приклад 9.1. Нехай L=L (r), де r=(a | b) * a (a | b) (a | b).
недетермінірованного кінцевий автомат M, що допускає мова L:
