Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Автомати з магазинною пам’яттю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2008
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-32
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу дискретна математика
на тему:
„Автомати з магазинною пам’яттю. ”
АНОТАЦІЯ
В даній курсовій роботі розглядаються автомати з магазинною пам′яттю (МП-автомати).
Означення МП-автомата, а також варіанти МП-автоматів.
Розглядається еквівалентність МП-автоматів і контекстно вільних граматик (КВ-граматик).
Також подано детерміновані автомати з магазинною пам′яттю (ДМП-автомати), синтез МП-автомата. А в кінці програма реалізації синтезу ДМП-автомата.
Зміст
1. Вступ.....................................................................................3
2. Означення МП-автомата..................................................6
3. Варіанти МП-автоматів....................................................9
4.Еквівалентність МП-автоматів та КВ-мов...................14
5. Детерміновані МП-автомати...........................................16
6. Синтез магазинних автоматів.........................................22
7. Правила за якими синтезуються МП-автомати..........24
8. Висновок..............................................................................26
9. Список використаної літератури....................................27
10.Програмна реалізація синтезу ДМП-автомата..............28
Вступ
У роботі розглядатимуться положення пов’язані з функціонуванням автоматів з магазинною пам’яттю, їхні види, побудова тощо.
Скінченні автомати можуть вирішувати лише ті завдання, які вимагають фіксофаного і скінченого об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок: кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має свою „роль”, тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною.
Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам’ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазина (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна вносити у магазин і видаляти їх з нього по одному. При цьому видаляється завжди лише символ який був внесений у магазин останнім.
Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (МП–автомат). У ньому дуже просто поєднується пам’ять скінченого автомата і магазинна пам’ять.
Як і у випадку скінченого автомата, обробка скінченого ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок:
переходу у новий стан;
заштовхування символу в магазин;
виштовхування символу з магазина;
зчитування символу зі вхідного ланцюжка.
Отже, наведено достатньо фактів, які підтверджують актуальність опрацювання питання про автомати з магазинною пам’яттю.
Означення МП-автомата
Автомат з магазинною пам’яттю — розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомати з магазинною пам’яттю відомі також як МП–автомати.
Магазинний автомат – це зазвичай скінченний автомат, який називають керуючим, в якого, крім вхідного і вихідного каналів, є ще канал для роботи з магазином. Магазин являє собою пам'ять, яка має назву магазинної пам'яті, де може зберігається одне слово в деякому алфавіті. Цей алфавіт називається магазинним алфавітом і, взагалі кажучи, може відрізнятися від вхідного і вихідного алфавітів автомата. Магазин зручно зображати у вигляді послідовності комірок пам’яті, перенумерованих числами натурального ряду і розміщених по вертикалі таким чином, що перша комірка завжди стає верхньою. Слово із символів магазинного алфавіту розміщається у верхніх комірках магазину, а решта заповнюється спеціальним порожнім символом, відмінним від символів алфавіту . Магазин може працювати в двох режимах: читання і запису. При читанні сприймається буква, що знаходиться в комірці. При цьому буква витирається з цієї комірки, а частина слова, що залишається в магазині, зміщується на одну комірку вверх. В режимі запису, навпаки, слово, що зберігається в магазині, зміщується вниз на одну комірку, а в комірку, яка при цьому звільнилася, записується відповідний символ.
Представимо магазин(або магазинний список, або магазинну стрічку) у вигляді стрічки символів, до того ж верхнім елементом магазина буде вважатися найлівіший чи найправіший символ стрічки в залежності від того, що зручніше в даній ситуації. Поки що будемо вважати верхнім найлівіший символ стрічки, яка представляє магазинний список.
Означення1:Автомат з магазинною пам’яттю(скорочено МП-автомат) ─ це алгебраїчна структура
P= <Q, ∑, Г, δ, q0, Z0, F>, де
(1) Q ─ кінцева множина символів станів, що представляють всеможливі стани керуючого пристрою;
(2) ∑ ─ кінцевий вхідний алфавіт;
(3) Г ─ кінцевий алфавіт магазинних станів;
(4) δ ─ відображення множини Q×(∑ ∪ {e})×Г у множину кінцевих підмножин множини Q×Г*;
(5) q0 є Q ─ початковий стан керуючого пристрою;
(6) Z0 є Г ─ символ, що знаходиться в магазині в початковий момент (початковий символ);
(7) F( Q─ множина заключних станів.
Конфігурацією автомата з магазинною пам’яттю P називається трійка
(q, ω, α) є Q×∑*× Г*, де
q─поточний стан керуючого пристрою;
ω─невикористана частина вхідної стрічки; перший символ стрічки ω знаходиться під вхідною головкою; якщо ω=℮, то вважається, що вся вхідна стрічка прочитана;
(3) α─вміст магазину; найлівіший символ стрічки α вважається верхнім символом магазина; якщо α=℮, то магазин вважається пустим.
Такт роботи автомата з магазинною пам’яттю P представимо у вигляді бінарного відношення |─p (чи |─, коли мається на увазі P), визначеного на конфігураціях. Будемо писати:
(q,aω,Z()|─(q/,ω,(() (1)
якщо множина δ( q, a, Z) містить (q/, (), де q, q/ ( Q, a ( ∑∪{℮}, ω ( ∑*, Z (Г і (, ( ( Г*.
Якщо a ≠ ℮, то (1) говорить про те, що МП-автомат P, знаходячись у стані q і маючи a у ролі текучого вхідного символу, розміщеного під вхідною головкою, а Z─ у якості верхнього символу магазину, може перейти в новий стан q/, змістивши вхідну головку на одну клітинку вправо і замінити верхній символ магазину ланцюжком ( магазинних символів. Якщо (=℮, то верхній символ видаляється із магазину, і тим самим магазинний список скорочується.
Якщо a = ℮, то будемо називати цей такт ℮-тактом. В ℮-такті вхідний символ не береться до уваги і вхідна головка не зрушується. Однак стан керуючого пристрою і вміст пам’яті можуть змінюватися. Зауважимо, що ℮-такт може відбуватись і тоді, коли вся вхідна стрічка прочитана.
Наступний такт не можливий, якщо магазин пустий.
Можна звичайним чином визначити відношення |─ί для ί≥0, |─* і |─+, а саме : |─* і |─+ ─це відповідно рефлексивно-транзитивне і транзитивне замикання відношення |─.
Початковою конфігурацією МП-автомата P називається конфігурація виду (q0, ω, Z0), де ω ( ∑*, тобто керуючий пристрій знаходиться у початковому стані, вхідна стрічка містить ланцюжок, який потрібно розпізнати, а у магазині є тільки початковий символ Z0. Заключна конфігурація ─ це конфігурація виду (q, ℮, (), де q ( F і ( ( Г*.
Говорять, що стрічка ω допускається МП-автоматом P, якщо (q0, ω, Z0) |─* (q, ℮, () для деяких q ( F і ( ( Г*. Мовою визначеною(чи допущеною) автоматом P(позначається L(P)) називають множину ланцюжків, що допускаються автоматом P.
Приклад 1. Побудуємо МП-автомат, що визначає мову L={0n1n|n≥0}. Нехай P=({q0, q1, q2}, {0,1}, {Z, 0}, (, q0, Z, {q0}), де
((q0, 0, Z)= {(q1, 0Z)}
((q1, 0, 0)= {(q1, 00)}
((q1, 1, 0)= {(q2, ℮)}
((q2, 1, 0)= {(q2, ℮)}
((q2, ℮, Z)= {(q0, ℮)}
Робота МП-автомата P полягає в тому, що він копіює в магазині початкову частину вхідного ланцюжка, що складається з нулів, а потім видаляє із магазину по одному нулю на кожну одиницю, яку він бачить на вході. Крім того, переходи станів гарантують, що всі нулі передують одиницям. Наприклад, для вхідного ланцюжка 0011 автомат P зробить таку послідовність тактів:
(q0, 0011, Z) |─ (q0, 0011, Z)
|─ (q1, 11, 00Z)
|─ (q2, 1, 0Z)
|─ (q2, ℮, Z)
|─ (q0, ℮, ℮)
Взагалі можна показати, що:
(q0, 0, Z) |─ (q1, ℮, 0Z)
(q1, 0ί, 0Z) |─ί (q1, ℮, 0ί+1Z)
(q1, 1, 0ί+1Z) |─ (q2, ℮, 0ίZ)
(q2, 1ί, 0ίZ) |─ί (q2, ℮, Z)
(q2, ℮, Z) |─ (q0, ℮, ℮)
Об’єднуючи все це, отримуємо для n≥1
(q0, 0n1n, Z) |─2n+1 (q0, ℮, ℮)
і
(q0, ℮, Z) |─0 (q0, ℮, Z)
Таким чином, L(L(P).
Покажемо, що L(L(P), тобто, що P допускає тільки ланцюжки виду 0n1n. Ця частина доведення складніша. Зазвичай легше довести, що такі-то ланцюжки розпізнавач допускає, і так само, як і для граматик складніше довести, що він допускає ланцюжки тільки визначеного виду.
В даному випадку замітимо, що якщо P допускає не порожній ланцюжок, то він повинен пройти через стани q0, q1, q2, q0 саме в цьому порядку.
Дальше, якщо (q0, ω, Z) |─ί (q1, ℮, () для ί≥1, то ω=0ί і (=0ί Z. Аналогічно, якщо (q2, ω, () |─ί (q2, ℮, (), то ω=1ί і (=0ί (. До того ж (q1, ω, () |─ (q2, ℮, () тільки тоді, коли ω=1 і (=0(, а (q2, ω, Z) |─* (q0, ℮, ℮) тільки тоді, коли ω=℮. Таким чином, якщо (q0, ω, Z) |─ί (q1, ℮, () для деякого ί≥0, то або ω=℮ і ί=0, або ω=0n1n, ί=2n+1, і (=℮. Отже, L(L(P).(
Зауважимо ще раз, що МП-автомат, як ми його означили, може продовжувати роботу (робити ℮-такти), навіть якщо він прочитав вже весь вхідний ланцюжок. Але він не може робити наступний такт, якщо його магазин пустий.
Зауважимо, що хоча недетермінований МП-автомат може забезпечити зручне абстрактне визначення мови, для реалізації на практиці потрібно промоделювати його детерміновано.
Варіанти МП-автоматів.
Розглянемо один фундаментальний аспект поведінки МП-автомата, який інтуїтивно представляється зовсім явним. Його можна сформулювати так: «Те, що відбувається із верхнім символом магазина, не залежить від того, що знаходиться в магазині під ним.»
Лема 1: Нехай P= (Q, ∑, Г, δ, q0, Z0, F )─МП-автомат.
Якщо (q, ω, А) |─n (q/, ℮, ℮), то (q, ω, А() |─n (q/, ℮, () для всіх A( Г і ( ( Г*.
Доведення: Доведення індукцією по n досить просте. Для n=1 лема, очевидно, вірна. Припустимо, що вона вірна для всіх 1≤ n< n/, і нехай
(q, ω, А) |─n′(q/, ℮, ℮). Тоді відповідна послідовність тактів повинна мати вигляд:
(q, ω, А)|─ (q1, ω1, Х1…Xk)
|─ ⁿ₁ (q2, ω2, Х2…Xk)
.
.
.
|─ ⁿκ₋₁ (qk, ωk, Xk)
|─ ⁿκ (q/, ℮, ℮)
де k(1 і nί ( n′ для 1≤ί≤ k.
Тоді для будь-яких ( ( Г* також можлива послідовність
(q, ω, А()|─ (q1, ω1, Х1…Xk()
|─ ⁿ₁ (q2, ω2, Х2…Xk()
.
.
.
|─ ⁿκ₋₁ (qk, ωk, Xk()
|─ ⁿκ (q/, ℮, ()
Всюди, крім першого такту, для доведення ми користувались представленням індукції.
Лему доведено. (
Тепер ми трохи розширимо означення МП-автомата, дозволивши йому заміняти за один такт стрічку символів обмеженої довжини, розташовану у верхній частині магазину, другою стрічкою скінченої довжини. Нагадаємо, що МП-автомат у початковій версії міг на даному такті заміняти лише один верхній символ магазину.
Означення 2. Розширеним МП-автоматом назвемо сімірку
P= <Q, ∑, Г, δ, q0, Z0, F>, де δ─ відображення кінцевої підмножини множини
Q× (∑ ∪ {e}) ×Г* у множину кінцевих підмножин множини Q×Г*, а всі інші символи мають те саме значення, що й раніше.
Конфігурація визначається так само, як і раніше, і ми пишемо:
(q, aω, (() |─ (q′, ω, ((), якщо ((q, a, a) містить (q′, (), де q ( Q, a ( ∑ ∪ {e} і ( ( Г*. В цьому такті ланцюжок (, розміщений у верхній частині магазину, заміняється ланцюжком (. Як і раніше, мовою L(P), що визначається автоматом P, називається множина:
{ω| (q0, ω, Z0) |─* (q, ℮ , () для деяких q ( F і ( ( Г*}.
Зауважимо, що на відміну від звичайного МП-автомата розширений МП-автомат володіє можливістю продовжувати роботу і тоді, коли магазин пустий.
Приклад 2.Визначимо розширений МП-автомат P, який розпізнає мову
L={ ωωR| ω ( {a, b}*}. Нехай P=({q, p}, {a, b }, {a, b, S, Z }, (, q, Z, {p}), де
(1) ((q, a, ℮)= {(q, a)}
(2) ((q, b, ℮)= {(q, b)}
(3) ((q, ℮, ℮)= {(q, S)}
(4) ((q, ℮, aSa )= {(q, S)}
(5) ((q, ℮, bSb)= {(q, S)}
(6) ((q, ℮, SZ)= {( p, ℮)}
На вході aabbaa автомат P може зробити наступну послідовність тактів:
(q, aabbaa, Z)|─ (q, abbaa, aZ)
|─ (q, bbaa, aaZ)
|─ (q, baa, baaZ)
|─ (q, baa, SbaaZ)
|─ (q, aa, bSbaaZ)
|─ (q, aa, SaaZ)
|─ (q, a, aSaaZ)
|─ (q, a, SaZ)
|─ (q, ℮, aSaZ)
|─ (q, ℮, SZ)
|─ (p, ℮, ℮)
Робота автомата P полягає в тому, що спочатку він запасає у магазині деякий префікс вхідного ланцюжка. Потім верхнім символом магазину робиться маркер S, що вказує на передбачену середину вхідного ланцюжка. Потім P поміщає в магазин черговий вхідний символ і заміняє в магазині aSa чи bSb на S. Автомат P працює до тих пір, поки не закінчиться весь вхідний ланцюжок. Якщо після цього у магазині залишиться SZ, то P зітре SZ і попаде у кінцевий стан. (
Покажемо, що мова L визначається МП-автоматом тоді і тільки тоді, коли вона визначається розширеним МП-автоматом. Необхідність умови очевидна, доведемо достатність.
Лема 2. Нехай P= (Q, ∑, Г, δ, q0, Z0, F)─ розширений МП-автомат. Тоді існує такий МП-автомат P1, що L(P1)= L(P).
Доведення: Припустимо m=max {|(| | ((q, a, () (( для деяких q ( Q,
a ( ∑ ∪ {e} }. Побудуємо МП-автомат P1, який буде моделювати автомат P, зберігаючи верхні m символів його магазину в «буфері» довжини m, що займає частину кінцевої пам’яті керуючого пристрою автомата P1. Тоді P1 зможе сказати на початку кожного такту, якими є m верхніх символів магазину автомата P. Якщо у деякому такті P заміняє k верхніх символів магазину ланцюжком із l символів, то P1 замінить k перших символів у буфері цим ланцюжком довжини l. Якщо l( k, то P1 зробить k─l допоміжних ℮-тактів, протягом яких k─l символів перейдуть із верхньої частини магазину в буфер керуючого пристрою. Після цього буфер буде заповненим, і P1 готовий моделювати черговий такт автомата P. Якщо l( k, то символи передаються із буфера у магазин.
Отже, покладемо P1= (Q1, ∑, Г1, δ1, q1, Z1, F1), де
Q1= {[q, (] | q ( Q, ( ( Г1* , 0≤ |(|≤ m} ;
Г1= Г∪{ Z1 };
δ1 визначається так:
(а) Припустимо, що δ(q, a, Х1…Xk) містить (r, Y1…Yl).
(і) Якщо l( k, то для всіх Z( Г1 і ( ( Г1* , |(|= m-k,
δ1([q, Х1…Xk(], a, Z) містить ([r, (], (Z) де ((= Y1…Yl(
і |(|= m.
(іі) Якщо l(k, то для всіх Z( Г1 і ( ( Г1* , |(|= m-k,
δ1([q, Х1…Xk(], a, Z) містить
([r, Y1…Yl(Z], ℮).
(б) Для всіх q ( Q, Z( Г1 і ( ( Г1* , |(|( m,
δ1([q, (], ℮, Z) = {([ q, (Z], ℮)}.
Ці правила показують заповнення буфера керуючого пристрою, який містить m символів.
q1= [q0, Z0Z1m-1]. В початковий момент буфер містить Z0 нагорі і m-1 символів Z1 нижче. Символи Z1 використовуються як спеціальні маркери, що відмічають «дно», тобто нижній кінець магазина.
F1={[q, (] | q ( F, ( ( Г1*}.
Неважко показати, що:
(q, aω, Х1…XkXk+1… Xn) |─P(r,ω,Y1…Yl Xk+1… Xn) тоді і тільки тоді, коли
([q, (], aω, () |─+P₁ ([q, (′], ω, (′), де
(1) ((= Х1… XnZ1m
(2) (′(′= Y1…Yl Xk+1… XnZ1m
(3) |(|=|(′|= m
(4) між двома вказаними конфігураціями МП-автомата P1 немає ні однієї конфігурації, стан якої мав би другу компоненту (буфер) довжиною m.
Для цього достатньо безпосередньо використати правила, що визначають P1.
Таким чином, (q0, ω, Z0) |─*P (q, ℮, () для деяких q ( F і ( ( Г* тоді і тільки тоді, коли
([q0, Z0Z1m-1], ω, Z1) |─*P₁ ([q, (], ℮, ()
де |(|= m і ((=( Z1m. Звідси L(P1)= L(P). Лему доведено. (
Тепер дослідимо вхідні стрічки, що заставляють МП-автомат очищувати магазин.
Означення 3: Нехай P= <Q, ∑, Г, δ, q0, Z0, F> ─ МП-автомат чи розширений МП-автомат. Будемо говорити, що P допускає стрічку ω (∑* очищенням магазину, якщо (q0, ω, Z0) |─+ (q, ℮, ℮) для деякого q ( Q. Нехай L℮(P)─ множина стрічок, що допускаються автоматом P очищенням магазину.
Лема 3. Нехай L= L(P) для деякого МП-автомата P= (Q, ∑, Г, δ, q0, Z0, F). Можна побудувати такий МП-автомат P′, що L℮(P′)= L.
Доведення: Нехай P′ моделює P. Кожен раз коли P переходить у заключний стан, P′ вирішує, продовжувати моделювання P чи перейти у спеціальний стан q℮, який очистить магазин. Проте є одне ускладнення. Для деякої вхідної стрічки ω автомат P може зробити послідовність тактів, що приведе до очищення магазину, а керуючий пристрій опиниться при цьому не в заключному стані. Тоді для того, щоб зашкодити P′ допустити в цьому випадку стрічку ω, додамо до P′ спеціальний маркер, який відмічає дно магазину і який автомат P′ може знищити тільки у стані q℮. Формально покладемо:
P′= (Q∪{ q℮, q′}, ∑, Г∪ {Z′}, δ′, q′, Z′, ()(для МП-автоматів, що допускають мову очищенням магазину, множина заключних станів зазвичай береться пустою.), де δ′ визначається так:
(1) якщо δ(q, a, Z) містить (r, (), то δ′(q, a, Z) містить (r, () для всіх q ( Q,
a ( ∑ ∪ {℮} і Z ( Г;
(2) δ′(q′, ℮, Z′)={(q0, Z0Z′)}, тобто на першому такті автомат P′ записує в магазин Z0Z′ і переходить в початковий стан автомата P (Z′ виконує роль маркера, який відмічає дно магазину);
(3) для всіх q(F і Z(Г∪ {Z′} множина δ′(q, ℮, Z) містить (q℮, ℮);
(4) δ′(q℮, ℮, Z)= {(q℮, ℮)} для всіх Z(Г∪{Z′}. Легко бачити, що
(q′, ω, Z′) |─P′ (q0, ω, Z0Z′)
|─nP′ (q, ℮, Y1…Yr)
|─P′ (q℮, ℮, Y2…Yr)
|─r-1P′ (q℮, ℮, ℮)
де Yr= Z′, тоді і тільки тоді, коли
(q0, ω, Z0) |─nP (q, ℮, Y1…Yr-1)
для всіх q(F і Y1…Yr-1 ( Г*. Отже, L℮(P′)= L(P).
Лему доведено. (
Обернене твердження леми також справедливе.
Лема 4. Нехай P= (Q, ∑, Г, δ, q0, Z0, ()─МП-автомат. Можна побудувати такий МП-автомат P′, що L(P′)=L℮(P).
Доведення: P′ буде моделювати P, використовуючи у поточний момент спеціальний символ Z′, що знаходиться на дні магазину. В той момент, коли автомат P′ може прочитати Z′, він буде переходити в новий заключний стан qf. Далі лема доводиться аналогічно до леми 3.
Лему доведено. (
Результати попередніх лем і означень можна сформувати у вигляді наступної теореми.
Теорема: Твердження:
L= L(P1) для МП-автомата P1,
L= L℮(P2) для МП-автомата P2,
L= L(P3) для розширеного МП-автомата P3
еквівалентні.
Доведення: Із (3) випливає (1) за лемою 2, а з (3) тривіально випливає (1). Із (1) випливає (2) за лемою 3, і із (2) випливає (1) за лемою 4.
Теорему доведено. (
Еквівалентність МП–автоматів та КВ–мов
Продукція граматики дає змогу замінювати одну послідовність символів іншою. Граматики класифікують за типами продукцій. Найчастіше використовують класифікацію, яку запропонував Н. Хомський.
Типи граматик
Обмеження на продукції
0
Немає обмежень
1
або , – ланцюжок
2
, де – нетермінальний символ
3
, причому або , де , – нетермінальні символи, – термінальний символ, або , або
Граматика типу 2 має продукції лише у формі , де – нетермінальний символ. Цю граматику називають контекстно вільною, оскільки нетермінал може бути замінений ланцюжком у довільному оточенні щоразу, коли він зустрічається, тобто незалежно від контексту.
Граматику типу 1 називають контекстно залежною. Коли у такій граматиці є продукція (тобто , ), у якій хоча б один з ланцюжків , відмінний від , то термінал може бути замінений ланцюжком лише в оточенні та , тобто у відповідному контексті, звідси походить назва.
Граматику типу 3 називають регулярною. Ця граматика може мати лише продукції у формі , , , де , – нетермінали, – термінал.
Відповідно до граматик відбувається й класифікація мов. Мову називають контекстно залежною, якщо існує контекстно залежна граматика, яка породжує цю мову. Мову називають контекстно вільною, якщо існує контекстно вільна граматика, яка породжує цю мову. Аналогічно для двох інших типів мов.
Поняття недетермінованості скінченного розпізнавача набуває практичного значення завдяки наступному факту – для кожного недетермінованого скінченного розпізнавача існує детермінований скінчений розпізнавач, який допускає в точності ті ж вхідні ланцюжки, що і недетермінований.
Процедура задається п'ятьма кроками. Нехай – недетермінований автомат, а – еквівалентний йому детермінований, которий потрібно побудувати.
1 крок. Замінити перший рядок таблиці переходів для множиною початкових станів автомата .
2 крок. За даною множиною станів , що позначає рядок таблиці переходів автомата , для якої переходи ще не вираховані, обчислити ті стани , які можуть бути досягнуті за допомогою кожного вхідного символу , і помістити множини подальших станів у відповідні елементи таблиці для .
Символічно це виражається так: якщо – функція недетермінованих переходів, то функція детермінованих переходів задається формулою .
3 крок. Для кожної нової множини, породженї переходами на кроці 2, подивитись, чи є вже в рядок, помічений станом. Якщо немає, то створити новий рядок і помітити його станом. Якщо множина вже використовувалася як цільова, нияких дій не вимагається.
4 крок. Якщо в таблиці автомата є рядок, для якого ще не обчислені переходи, повернутися назад і застосувати до цього рядка крок 2, інакше перейти до кроку 5.
5 крок. Відмітити рядок як додатковий стан автомата тоді, коли він містить допустимий стан недетермінованного автомата. Інакше відмітити як виштовхуючий стан.
Приклад 3. Побудувати МП–автомат, для якого , де – граматика, що визначає арифметичні вирази.
Нехай , де визначається так:
для всіх .
При вході для можлива інша послідовність тактів:
.
Відмітимо, що обчислення МП–автомата відповідає лівому виводу ланцюжка з в КВ–граматиці G.
Тип синтаксичного аналізу, що проводиться МП–автоматом, називається низхідним аналізом.
Можна побудувати розширений МП–автомат, який працює від низу до верху як висхідний аналізатор.
Детерміновані МП-автомати.
Ми вже бачили, що для кожної КВ-граматики G можна побудувати МП-автомат, що розпізнає L(G). Однак побудований МП-автомат був недетермінований. В практичних застосуваннях нас більше цікавлять детерміновані МП-автомати, тобто такі, які в кожній конфігурації можуть зробити не більше одного чергово такту. В цьому розділі ми займемося детермінованими МП-автоматами і в подальшому побачимо, що, на жаль, детерміновані МП-автомати не такі потужні по своїй розпізнавальній можливості, як недетерміновані МП-автомати. Існують КВ-мови, які не можна визначити детермінованими МП-автоматами.
Мова, яка визначається детермінованим МП-автоматом, називається детермінованою контекстно-вільною мовою.
Означення 4: МП-автомат P=<Q, ∑, Г, δ, q0, Z0, F> називається детермінованим(скорочено ДМП-автомат), якщо для кожних q ( Q і Z ( Г або
δ(q, a, Z) містить не більше одного елемента для кожного a (∑ і
δ(q, ℮, Z)=(, або
δ(q, a, Z)= ( для всіх a (∑ і δ(q, ℮, Z) містить не більше одного елемента.
В силу цих двох обмежень ДМП-автомат в будь-якій конфігурації може вибрати не більше одного такту. Це приводе до того, що на практиці набагато легше моделювати детермінований МП-автомат, ніж недетермінований. По цій причині клас детермінованих КВ-мов важливий для практичного застосування.
Домовимось: так як для ДМП-автомата δ(q, a, Z) містить не більше одного елемента, ми будемо писати δ(q, a, Z)= (r, () замість δ(q, a, Z)={(r, ()}.
Означення детермінованого МП-автомата можна розширити, щоб включити в нього ті розширені МП-автомати, які природно вважати детермінованими.
Означення 5: Розширений МП-автомат P=(Q, ∑, Г, δ, q0, Z0, F) називається детермінованим, якщо виконані наступні умови:
# δ(q, a, () ≤1 для всіх q ( Q, a (∑∪{℮} і (( Г*;
якщо δ(q, a, ()((, δ(q, a, ()(( і (((, то жоден із ланцюжків ( і ( не є суфіксом другого(якщо верх магазину розширеного МП-автомата розміщений зліва, то тут потрібно «суфікс» замінити на «префікс».)
якщо δ(q, a, ()(( і δ(q, ℮, ()((, то жоден із ланцюжків ( і ( не являється суфіксом другого.
Легко бачити, що в тому випадку, коли розширений МП-автомат є звичайним ДМП-автоматом, це означення співпадає з попереднім. Крім того, якщо конструкція леми 2 застосовується до розширеного МП-автомату, результатом буде детермінований МП-автомат тоді і тільки тоді, коли детермінованим був вихідний розширений МП-автомат.
При моделюванні синтаксичного аналізатора бажано мати ДМП-автомат P, який зчитує всю вхідну стрічку, навіть якщо не належить мові L(P). Покажемо, що такий ДМП-автомат завжди можна знайти.
Спочатку модифікуємо ДМП-автомат так, щоб для будь-якої конфігурації, в якій частина входу залишилась непрочитаною, завжди був можливий черговий такт. Наступна лема показує, як це зробити.
Лема 5. Нехай P=(Q, ∑, Г, δ, q0, Z0, F)─ДМП-автомат. Можна побудувати такий еквівалентний ДМП-автомат P′=(Q′, ∑, Г′, δ′, q′0, Z′0, F), що
для всіх a(∑, q(Q′ і Z(Г′ або
(а) δ′(q, a, Z) містить лише один елемент і δ′(q, ℮, Z) ((, або
(б) δ′(q, a, Z) (( і δ′(q, ℮, Z) містить лише один елемент;
(2) якщо δ′(q, a, Z′0)= (r, () для деякого a(∑∪{℮}, то (=( Z′0 для деякого ланцюжка a( Г*.
Доведення: Символ Z′0 буде працювати як маркер, що вказує на кінець магазину(дно) і попереджує повне очищення магазину. Нехай Г′= Г∪{Z′0} і
Q′={ q′0, q℮}∪Q, а δ′ визначається так:
δ′( q′0, ℮, Z′0)= ( q0, Z0Z′0);
для всіх q(Q, a(∑∪{℮} і Z(Г, таких, що δ(q, a, Z) ((, припускаємо
δ′(q, a, Z) ( δ(q, a, Z);
якщо δ(q, ℮, Z) (( і δ(q, a, Z) (( для деяких a(∑ і Z(Г, припускаємо δ′(q, a, Z)= (q℮, Z);
для всіх Z(Г′ і a(∑ припускаємо δ′( q℮, a, Z)= (q℮, Z).
За правилом (1) P′ запише у верхній частині магазину Z0Z′0 і, перейшовши у стан q0, почне моделювати P. Правила (2) дозволяють P′ моделювати P, доки наступний такт стане неможливим. В цій ситуації P′(за правилом 3) перейде у незаключний стан q℮ і залишиться у ньому, не змінюючи вмісту магазину, поки не буде прочитана частина входу, що залишилась. ( L(P′)=L(P).
Лему доведено. (
ДМП-автомат може, виходячи із певної конфігурації, зробити безкінечне число ℮-тактів, не прочитавши більше ні одного вхідного символу. Таку конфігурацію ми назвемо зациклюючою.
Означення 6: Конфігурація (q, ω, () ДМП-автомата P називається зациклюючою, якщо для кожного ί≥1 найдеться така конфігурація (pί, ω, (ί), що |(ί|≥( і (q, ω, () |─(p1, ω, (1) |─(p2, ω, (2) |─…
Таким чином, конфігурація зациклююча, якщо P може зробити безкінечне число ℮-тактів, не скорочуючи магазину; при цьому магазин може або безкінечно зростати, або циклічно співпадати з деякими різними ланцюжками.
Зауважимо, що існують незациклюючі конфігурації, які після ряду ℮-тактів, скорочуючи магазин, переходять у зациклюючу конфігурацію. Ми покажемо, що не можна зробити безкінечне число ℮-тактів, виходячи із будь-якої даної конфігурації, не попавши через кінцеве і при тому злічене число тактів у зациклюючи конфігурацію.
Якщо P попадає у зациклюючи конфігурацію в середині вхідної стрічки, то він більше не буде використовувати вхідну стрічку, навіть якщо задовольняє лему 8. Ми хочемо перетворити даний ДМП-автомат P в еквівалентний ДМП-автомат P′, який ніколи не попадає в зациклюючи конфігурацію.
Алгоритм 1. Знаходження зациклюючи конфігурацій.
Вхід. ДМП-автомат P=(Q, ∑, Г, δ, q0, Z0, F).
Вихід. (1) C1 = {(q, A)| (q, ℮, A) ─ зациклююча конфігурація і не існує такого r(F, що (q, ℮, A) |─*(r, ℮, () для деякого ланцюжка (( Г*} і
(2) C2 = {(q, A)| (q, ℮, A) ─ зациклююча конфігурація і (q, ℮, A) |─*(r, ℮, () для деяких r(F і (( Г*}.
Метод. Нехай #Q=n1, #Г=n2 і l ─ довжина найдовшого ланцюжка, який P може записати в магазин за один такт. Нехай n3= n1(n2n₁n₂l+1- n2)/(n2-1), якщо n2(1, і n3= n1, якщо n2=1. Число n3─ це максимальне число ℮-тактів, які може зробити P, не зациклюючись.
(1) Для всіх q(Q і A(Г визначити, чи виконується (q, ℮, A) |─n₃ (r, ℮, () для яких-небудь r(Q і (( Г+. При цьому використовується пряме моделювання P. Якщо так, то (q, ℮, A) ─ зациклююча конфігурація, так як в цьому випадку ─ ми це покажемо ─ повинна бути така пара (q′, A′), де q′(Q і A′(Г, що
(q, ℮, A) |─* (q′, ℮, A′()
|─m (q′, ℮, A′(()
|─m(j-1) (q′, ℮, A′(j()
де m(0 і j(0. Зауважимо, ( може бути ℮.
Якщо (q, ℮, A) ─ зациклюючи конфігурація, з’ясувати, чи існує таке r(F, що (q, ℮, A) |─ j (r, ℮, () для деякого 0( j( n3. При цьому знову використовується пряме моделювання. Якщо так, то включити (q, A) в C2. В противному випадку включити (q, A) в C1. Ми стверджуємо, що якщо P досягнути заключної конфігурації, виходячи із (q, ℮, A), то це повинно статися за n3 або менше число тактів. (
Теорема . Алгоритм 1 правильно знаходить множини C1 і C2.
Доведення: Спочатку доведемо, що крок (1) правильно визначає множину C1∪C2. Якщо (q, A)(C1∪C2, то очевидно, що (q, ℮, A) |─n₃(r, ℮, (). Навпаки, припустимо, що (q, ℮, A) |─n₃(r, ℮, ().
Випадок 1. Існує такий ланцюжок ((Г*, що |(|( n1n2l і
(q, ℮, A)|─*(p, ℮, ()|─* (r, ℮, () для деякого p(Q. Якщо в послідовності тактів
(q, ℮, A)|─*(p, ℮, () для кожного j=1, 2,… n1n2l+1 виділити конфігурацію, в якій знаходиться P, коли довжина його магазину в останній раз стає рівною j, то можна замітити, що у виділеній послідовності конфігурацій деякий стан q′ і символ A′ повинні двічі зустрічатись в якості поточного стану і верхнього символу магазину; іншими словами, можна писати:
(q, ℮, A) |─* (q′, ℮, A′δ) |─+ (q′, ℮, A′(δ)|─*(p, ℮, (). Таким чином, за лемою 1
(q, ℮, A) |─* (q′, ℮, A′δ) |─mj (q′, ℮, A′(jδ) для всіх j≥0. Тут m≥0, тому, виходячи із конфігурації (q, ℮, A), можна зробити безкінечно багато ℮-тактів і, очевидно,
(q, A)(C1∪C2.
Випадок 2. Припустимо, що на противагу випадку 1 |(|( n1n2l для всіх таких (, що (q, ℮, A)|─*(p, ℮, ()|─* (r, ℮, (). Так як в цій послідовності конфігурацій мається n3+1 різних (, число можливих станів рівно n1 і число можливих магазинних ланцюжків довжини, не більше n1n2l, рівно
n2+n²2+n32+…+ n2n₁n₂l = (n2n₁n₂l+1- n2)/(n2-1), то деяка конфігурація повинна повторятися. Звідси випливає, що (q, A)(C1∪C2.(крок 2 правильно розбиває множину C1∪C2 на множини C1 і C2).
Теорему доведено.(
Означення 7: ДМП-автомат P=(Q, ∑, Г, δ, q0, Z0, F) назвемо дочитуючим, якщо для кожної стрічки ω(∑* існують такі p(Q і (( Г*, що:
(q0, ω, Z0)|─*(p, ℮, (). Інтуїтивно, дочитуючим називається ДМП-автомат, який може дочитувати до кінця кожну вхідну стрічку.
Лема 6. Нехай P=(Q, ∑, Г, δ, q0, Z0, F)─ ДМП-автомат. Тоді існує еквівалентний йому дочитуючий ДМП-автомат P′.
Доведення: В силу леми 8 можна вважати, що для P завжди можливий черговий такт. Нехай P′=(Q∪{p, r}, ∑, Г, δ′, q0, Z0, F∪{p}), де p і r─ нові стани, а δ′ визначається так:
(1) для всіх q(Q, a(∑ і Z(Г положимо δ′(q, a, Z)= δ(q, a, Z);
(2) для всіх q(Q і Z(Г, таких, що, (q, ℮, Z) не є зациклюючою конфігурацією, покладемо δ′(q, ℮, Z)= δ(q, ℮, Z);
(3) для всіх (q, Z)(C1, де C1─ множина, побудована алгоритмом 1, покладемо δ′(q, ℮, Z)=δ(r, Z);
(4) для всіх (q, Z)(C2, де C2─ множина, побудована алгоритмом 1,покладемо δ′(q, ℮, Z)=δ(p, Z);
(5)для всіх a(∑ і Z(Г покладемо δ′( p,a,Z)=δ(r, Z) і δ′( r, a, Z)= δ(r, Z).
Таким чином, P′ моделює P, але якщо P попадає у зациклюючу конфігурацію, то P′ в черговому такті перейде у стан p чи r в залежності від того, зустрічається чи ні в циклічній послідовності конфігурацій заключний стан. Потім, яким би не був вхідний ланцюжок, P′ переходить в стан r і залишається у ньому, нічого не змінюючи у магазині. Звідси L(P′)=L(P).
Треба показати, що P′ ─ дочитуючий ДМП-автомат. Правила (3) ─ (5) гарантують, що умова «дочитування» для P′ виконується, якщо P попадає у зациклюючи конфігурацію. Залишається тільки зауважити, що якщо P знаходиться в незациклюючій конфігурації, то через кінцеве число тактів він повинен або:
(1) зробити не ℮-такт, або
(2) попасти у конфігурацію, що скорочує магазин.
Крім того, ситуація (2) не може повторятися безкінечно, оскільки в початковій конфігурації магазин має скінчену довжину. Таким чином, або в кінці кінців відбудеться (1), або після декількох повторень (2) P потрапить в зациклюючу конфігурацію. Отже, можна зробити висновок, що ДМП-автомат P′ дочитуючий.
Лему доведено. (
Тепер доведемо одну важливу властивість ДМП-автоматів, а саме, що клас мов, які вони розпізнають, є замкненим відносно доповнення.
Теорема. Якщо L=L(P) для деякого ДМП-автомата P, то L=L(P′) для деякого ДМП-автомата P′.
Доведення: За лемою 6 можна вважати, що P─ дочитуючий. Побудуємо P′ так, щоб він моделював P і між зрушеннями вхідної головки виясняв, чи попав P у допустимий стан. Так як P′ повинен допускати доповнення мови L(P), то P′ допускає вхідний ланцюжок, якщо P не допускає його і збирається зрушити свою вхідну головку(і, очевидно, вже не допустить її і пізніше).
Формально нехай P=(Q, ∑, Г, δ, q0, Z0, F) і
P′=(Q′, ∑, Г, δ′, q′0, Z0, F′), де
(1) Q′={[q, ί] | q(Q, ί({0, 1, 2}},
(2) q′0=[q0, 0], якщо q0( F і q′0=[q0, 1], якщо q0(F,
(3) F′={[q, 2] | q(Q}.
Стани виду [q, 0] призначені для позначення того, що P не був у заключному стані після останнього не ℮-такту. Стани виду [q, 1] показують, що в даний момент P перейшов у заключний стан. Стани виду [q, 2] використовуються тільки для позначення заключних станів. Якщо P′ знаходиться в стані [q, 0] і у відповідний момент розпізнавач P, який моделюється, зробить не ℮-такт, то P′ спочатку переходить у стан [q, 2], а потім моделює P. Таким чином, P′ допускає тоді і тільки тоді, коли P не допускає. Той факт, що ДМП-автомат P ─ дочитуючий, гарантує, що і у P′ завжди є шанс допустити вхідний ланцюжок, якщо P не допускає його. Формальне визначення функції δ таке:
(1) якщо q(Q, a(∑ і Z(Г, то
δ′([q, 1], a, Z)= δ′([q, 2], a, Z)= ([p, ί], ()
де δ(q, a, Z)= (p, (), ί=0, якщо p( F, і ί=1, якщо p(F;
(2) якщо q(Q, Z(Г і δ(q, ℮, Z)= (p, (), то
δ′([q, 1], ℮, Z)= ([p, 1], ()
δ′([q, 0], ℮, Z)= ([p, ί], ()
де ί=0, якщо p( F, і ί=1, якщо p(F;
(3) якщо δ(q, ℮, Z)=(, то δ′([q, 0], ℮, Z)= ([q, 2], Z).
Правило (1) відноситься до не ℮-тактів. Друга компонента стану правильно значення 0 чи 1. Правило (2) відноситься до ℮-тактів, і тут воно справляється із другою компонентою стану, як задумано. Правило (3) дозволяє P′ допускати вхідний ланцюжок тоді, коли P не допускає його.
Теорему доведено. (
Синтез магазинних автоматів
Алгоритм синтезу, який за КВ–граматикою будує магазинний автомат з початковим станом і єдиним заключним станом . Автомат сприймає мову , що породжується граматикою .
Вхідний алфавіт автомата збігається з термінальним алфавітом граматики . Магазинний алфавіт складається із символів нетермінального алфавіту і символів, які є двійниками термінальних: . Двійники введені для того, щоб виконувалась умова . Множину станів автомата опишемо в процесі задання функції переходів .
В початковому стані автомат записує символ в магазин і переходить в стан – єдиний заключний стан, знаходячись в якому автомат може читати символи з магазину.
Коли автомат читає з магазину символ (двійник термінального символу), то при цьому він переходить в стан, який позначається . Якщо після цього на вхід автомата подається символ , то він переходить в стан , а в решті випадків перехід із стану невизначений. Зазначимо, що множина – це всі стани автомата, в яких він може читати символи з вхідного каналу.
Якщо в стані автомат читає з магазину символ , то він переходить в стан . Із цього стану автомат може спонтанно перейти в один із станів , де – всі ті і тільки ті слова в алфавіті , для яких у граматиці є продукції . Якщо містить продукцію , то за стан вибирається стан . Із стану автомат за кілька тактів роботи (число цих тактів дорівнює довжині слова ) переходить у стан . При цьому він записує в магазин слово і перша буква цього слова буде в магазині верхньою. При переході зі стану , де , в стан як проміжні використовуються стани і т. д. В стані автомат записує в магазин символ , якщо або його двійник, якщо , і переходить в стан , якщо або , якщо . Таким чином, стани автомата , що забезпечують запис правих частин продукцій в магазин, можуть бути подані у вигляді , де – початкове підслово правої частини деякої продукції граматики . Початкові підслова різних продукцій можуть збігатися.
Нетермінальні символи читаються з магазину в послідовності, яка відповідає лівому виведенню слова в граматиці (виведення і
одержуються з застосуванням продукції до одного з нетермінальних символів, який називають лівим, якщо на кожному з кроків виведення продукція застосовується до найлівішого нетермінального символу).
Приклад 4. Синтезувати автомат, що сприймає мову , де .
Згідно з наведеним вище алгоритмом синтезу визначимо вхідний і магазинний алфавіти, а також множину станів автомата , що синтезується: ,
Слід зазначити, що описаний алгоритм не найкращий, оскільки побудовані за ним автомати не завжди прості. Так, у випадку праволінійних чи ліволінійних граматик мови, що породжуються цими граматиками, будуть регулярними, отже, можуть сприйматися скінченними автоматами. Описаний же алгоритм синтезу будує магазинний автомат, в якому магазин використовуться завжди. В цьому і полягає один з основних недоліків наведеного алгоритму синтезу.
Правила, за якими синтезується МП–автомат:
По правилах виводу КВ–граматики будуємо систему рівнянь, користуючись правилами побудови регулярних виразів:
S → AB#
A → mAf|d
B → xB|z
S = (AB#)
A =(mAf+d)
B = (xB+z)
1). Проіндексуємо всі нетермінальні символи, які входять в праву частину.
2). Проіндексовані нетермінальні символи утворюють внутрішній алфавіт МП –автомата.
3). Якщо права частина рівнянь містить більше одного дизюнктивного члена, переносимо його в круглі дужки.
4). Розділяємо всі символи вертикальними рисками, які будуть задавати внутрішні стани автомата.
5). Стан, який передує відкритій дужці, автоматично поширює свою дію на початки всіх дизюнктивних членів.
6). Стан, який стоїть після закритої дужки, поширює свою дію на кінці всіх дизюнктивни...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора