Детерміновані кінцеві автомати
Детермінований кінцевий автомат - набір з п'яти елементів: де Sigma - алфавіт, Q - безліч станів, s - початкова (стартове) стан, T - безліч допускають станів, delta - функція переходів.
Детермінований кінцевий автомат є спеціальним випадком недетермінірованного кінцевого автомата, в якому
• відсутні стани, що мають e-переходи;
• для кожного стану s і вхідного символу а існує не більше однієї дуги, що виходить із s і поміченої як а.
Детермінований кінцевий автомат має для будь-якого вхідного символу не більше одного переходу з кожного стану. Якщо для представлення функції переходів ДКА використовується таблиця, то кожен запис в ній є єдине стан. Отже, дуже просто перевірити, чи допускає даний ДКА деяку рядок, оскільки є не більше одного шляху від стартового стану, позначеного цим рядком. Наступний алгоритм імітує поведінку ДКА при обробці вхідного рядка.
Стану q автомата М і q 'автомата М' вважаються еквівалентними, якщо обидва автомата, отримавши одну і ту ж (будь-яку) вхідну послідовність символів, переробляють її в однакову вихідну послідовність.
Автомати М і М 'називаються еквівалентними, якщо для кожного стану автомата М існує еквівалентну йому стан автомата М' і навпаки.
Іншими словами, еквівалентні автомати реалізують однакові перетворення, але можуть мати різне число внутрішніх станів.
Поняття еквівалентності станів може бути застосовано і до одного автомата (формально можна вважати, що М і М 'збігаються). Для одного автомата еквівалентними будуть різні стани, через які одна і та ж вхідна послідовність символів перетворюється в однакову вихідну.
Автомати з магазинною пам'яттю. Мова, що допускається магазинним автоматом. Побудова автомата з магазинної пам'яттю. Функції переходу. Способи завдання функцій переходу автомата з магазинної пам'яттю.
КС-граматика визначає структуру ланцюжків і дозволяє будувати ланцюжки певної мови. Магазинні автомати, подібно розглянутим раніше кінцевим автоматам, дозволяють вирішувати для контекстно-вільних мов завдання розпізнавання, яка полягає в тому, що за заданою ланцюжку необхідно визначити чи належить вона заданому мови.
У роботах, пов'язаних з формальними мовами і граматиками, використовується модель магазинного автомата. що складається з вхідних стрічки, пристрої управління та допоміжної стрічки, званої магазином або стеком.
Вхідна стрічка поділяється на клітини (позиції). в кожній з яких може бути
записаний символ вхідного алфавіту. При цьому передбачається, що в невикористовуваних клітинах вхідний стрічки розташовані порожні символи e.
Допоміжна стрічка також розділена на клітини, в яких можуть розташовуватися символи магазинного алфавіту. Початок допоміжної стрічки називається дном магазину. Зв'язок пристрої управління з стрічками здійснюється двома головками. які можуть переміщатися уздовж стрічок.
Головка вхідний стрічки може переміщатися тільки в одну сторону - вправо або
Залишатися на місці. Вона може виконувати тільки читання. Головка допоміжної стрічки здатна виконувати як читання, так і запис, але ці операції пов'язані з переміщенням головки певним чином:
- при запису головка попередньо зсувається на одну позицію вгору, а потім символ заноситься на стрічку,
- при читанні символ, що знаходиться під головкою зчитується зі стрічки, а потім головка зсувається на одну позицію вниз, т.о.головка завжди встановлена проти останнього записаного символу. Позицію, що знаходиться в даний момент часу під головкою, називаютвершіной магазину.
де
P - вхідний алфавіт,
S - алфавіт станів,
sо - початковий стан,
sо Про S,
F - безліч кінцевих станів, F є підмножиною S,
H - алфавітмагазінних символів. записуються на допоміжну стрічку,
hо - маркер дна, він завжди записується на дно магазину, hо Про H,
f - функція переходів
f.
> X S x H ® S x H *.
якщо М-автомат - детермінований, і
f:
> X S x H ® M (S x H *).
якщо М-автомат - недетермінований.
Функція f відображає трійки (pi. Sj. Hk) в пари (sr. U). де u Про H * і hk - символ в вершині магазина, для детермінованого автомата або в безліч пар для недетермінірованного автомата.
Ця функція описує зміну стану магазинного автомата, що відбувається при читанні символу із вхідними стрічки і премещенія вхідний головки.
Надалі при побудові магазинних автоматів будуть потрібні два різновиди функцій переходів, що змінюють стан автомата без переміщення вхідний головки: 1) функція переходів з порожнім символом в якості вхідного символу:
яка, незалежно від того який символ знаходиться під Новомосковскюшей голівкою вхідний стрічки, наказує прочитати символ h з вершини магазину, змінити стан автомата на s 'і записати цепочкуb в магазин.
2) функція переходів з певною вхідною символом:
яка наказує зміна стану і запис ланцюжка в магазин за умови, що символ a Новомосковскется вхідний головкою, а в вершині магазина знаходиться символ h.
Ланцюжок a називається допустімойдля автомата М, якщо існує послідовність конфігурацій, в якій перша конфігурація є початковою c ланцюжком a. а остання - заключній. (Sо. A, hо) | - * (s1. $. $). де s1 Про F.
Безліч ланцюжків, що допускаються автоматом М, називається мовою, що допускаються або визначеним автоматом М, і позначається L (М).
ЕсліГ =
В основі докази лежить спосіб побудови магазинного автомата по заданій КС-грамматіке.Чтоби зробити процес побудови автомата більш простим і наочним, домовимося використовувати магазинні автомати з одним станом s0. Отже, нехай задана граматика Г =
в якості початкового стану автомата приймемо s0 і побудуємо функцію переходів так:
1. Для всіх A Про VA. таких що зустрічаються в лівій частині правил
® a. побудуємо команди виду:
2. Для всіх a ОVт побудуємо команди виду
3. Для переходу в кінцевий стан побудуємо команду
4. Початкову конфігурацію автомата визначимо у вигляді:
де w - задана ланцюжок, записана на вхідних стрічці.
Автомат, побудований за наведеними вище правилами, працює наступним чином. Якщо в вершині магазина знаходиться термінал, і символ, Новомосковскемий із вхідними стрічки, збігається з ним, то по команді типу (2) термінал видаляється з магазину, а вхідні головка зсувається. Якщо ж в вершині магазина знаходиться нетермінал, то виконується команда типу (1), яка замість терміналу записує в магазин ланцюжок, що представляє собою праву частину правила граматики. Отже, автомат, послідовно замінюючи нетермінали, що з'являються в вершині магазина, будує в магазині лівий висновок вхідний ланцюжка, видаляючи отримані термінальні символи, що збігаються з символами вхідного ланцюжка. Це означає, що кожна ланцюжок, яка може бути отримана за допомогою лівого виведення в граматиці Г, допускається побудованим автоматом М.
Конфігурацією автомата М називають трійку (s, a. G) Про S x P * x H *.
При цьому передбачається, що автомат Новомосковскет символ a. що знаходиться під головкою, і символ h.
що знаходиться в вершині магазина, визначає новий стан s 'і записує ланцюжок b в
магазин замість символу h. Якщо b = $. то верхній символ виявляється віддаленим з магазину.
Така зміна конфігурацій можлива, якщо функція f (s, a, h) визначена і їй належить
значення (s ', b). Описаний такт роботи виконується з переміщенням головки. Для опису роботи автомата нам буде потрібно інший вид такту, що призводить до зміни станів і магазину без переміщення вхідний головки. Якщо f 0 (s, e, h) визначена і їй належить значення (s ', b). то він визначає зміну конфігурацій так:
Таким чином, можуть бути три випадки при роботі автомата:
- f (s, a, h) визначена і виконується такт роботи,
- f (s, a, h) не визначена, але визначена функція f 0 (s, e, h) та виконується порожній такт.
- Функції f (s, a, h) і f 0 (s, e, h) не визначені, в цьому випадку подальша робота автомата неможлива.
У загальному вигляді дії, що задаються функцією переходів і виконуються автоматом, демонструє наступна форма запису:
f (s, <входной символ>, <магазинный символ>) = (S1. <заносимая цепочка>)
При цьому слід мати на увазі, що при виконанні такту спочатку Новомосковскется символ в вершині, а потім на його місце заноситься новий символ або ланцюжок. Окремі значення функції переходів часто називають командами магазинного автомата.
Початковою конфігурацією називається конфігурація (sо. A. Hо). де sо початкова стан і hо - маркер дна магазину, а заключній - конфігурація (s, $. $). де s належить множині кінцевих станів F.
Для позначення послідовності змінюють один одного конфігурацій домовимося
використовувати знак | - *. Таким чином послідовність
записується в скороченому вигляді так: