Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Автомати з магазинною пам’яттю. Контекстно-вільні граматики
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2006
Тип роботи:
Курсова робота
Предмет:
Дискретна математика
Група:
ПМ-31
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
кафедра прикладної математики
КУРСОВА РОБОТА
з курсу дискретна математика
на тему:
„Автомати з магазинною пам’яттю. Контекстно-вільні граматики”
ЗМІСТ
Вступ. Основні поняття теорії формальних мов і граматик............................................................................................................3
Означення МП-автомата……………………………………………………………….3
Варіанти МП-автоматів………………………………………………………………..6
Еквівалентність МП-автоматів і КВ-граматик……………………………………...10
Детерміновані МП-автомати…………………………………………………………16
Синтез МП-автомата………………………………….................................................21
Програмна реалізація синтезу ДМП-автомата……………………………………...23
Список використаної літератури…………………….................................................27
Основні поняття теорії формальних мов і граматик.
Для того, щоб зрозуміти теорію алгоритмічних мов, необхідно оперувати найпростішими, але найфундаментальнішими поняттями теорії формальних мов і граматик, мати чітку уяву про ієрархію мови – літера, слово, мова.
Отже, літера – це простий неподільний знак. Множина літер утворює алфавіт.
Ланцюжок (слово, стрічка) – це впорядкована скінченна послідовність літер алфавіту. ε–порожній ланцюжок, ланцюжок нульової довжини. Над ланцюжками допускаються операції конкатенації (об’єднання ланцюжків) та обертання стрічок.
Мовою LA, породженою алфавітом А, називається сукупність всіх стрічок, отриманих у даній мові. Дамо також означення граматики. Формальною породжуючою граматикою G називається четвірка <N,Т,Р,S> , де Т – скінченна не порожня множина символів, яка називається термінальним або основним словником граматики G; N – скінченна не порожня множина символів, що називається нетермінальним (допоміжним) словником граматики G, причому ТN=Ø, Т N=V –об’єднаний словник граматики G; S – початковий символ або аксіома граматики G, S – нетермінал і є головною метою граматики G; Р – скінченна множина правил граматики G, елемент цієї множини можна задати у вигляді пари (α , β); ця пара – правило виводу або правило підстановки і часто записується у вигляді α→β. Варто зауважити, що α,β{NТ}* (A*– множина всіх можливих ланцюжків над алфавітом А, A*=А0А1А2...Аn... і називається замиканням алфавіту А або повною ітерацією; є ще неповна ітерація:А+ = A* \{ε}). Правила підстановки називають також схемою граматики.
Означимо відношення G (відношення в граматиці G, надалі писатимемо без позначки внизу, коли розумітимемо про яку граматику йдеться) на множині (NT)* так: якщо αβγ – стрічка з (NT)* і β → δ – правило з Р, то αβγ αδγ. Транзитивне замикання відношення позначають через+ (φ + ψ читається: ψ виводима з φ нетривіальним чином), а його рефлексивне і транзитивне замикання: * (φ * ψ читається: ψ виводима з φ).
Існує чотири класи мов і граматик за Хомським, але ми користуватимемося класом, що містить так звані контексно-вільні мови (КВ-мови). Це – мови, що породжуються граматиками, які мають правила виводу такого виду: α→β, де αN, βV+, тобто ліві частини правил виводу мають лише один нетермінальний символ.
Означення МП-автомата
Автомат з магазинною пам’яттю—розпізнавач, який представляє собою звичайну модель синтаксичних аналізаторів контекстно-вільних мов. Автомат з магазинною пам’яттю—односторонній недетермінований розпізнавач , в потенційно нескінченній пам’яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожний момент доступний тільки верхній елемент магазина. Розпізнавач такого типу зображений на рисунку 1.
А1
А2
Аn
Вхідна стрічка
(тільки читати)
Z1
Z2
Zm
Магазин
Рис.1.Автомат з магазинною пам’яттю
В цій курсовій роботі буде доведено один фундаментальний результат, який відноситься до автоматів з магазинною пам’ятю, а саме: мова є контекстно-вільною тоді і тільки тоді, коли вона допускається не детермінованим автоматом з магазинною пам’яттю. Також буде розглянуто один підклас контекстно-вільних мов, які є особливо важливі з точки зору аналізу мов. Він складається із детермінованих контекстно-вільних мов, тобто мов, які розпізнаються детермінованими автоматами з магазинною пам’ятю.
Представимо магазин(або магазинний список, або магазинну стрічку) у вигляді стрічки символів, до того ж верхнім елементом магазина буде вважатися найлівіший чи найправіший символ стрічки в залежності від того, що зручніше в даній ситуації. Поки що будемо вважати верхнім найлівіший символ стрічки, яка представляє магазинний список.
Означення1:Автомат з магазинною пам’яттю(скорочено МП-автомат)─ це семірка
P= (Q, ∑, Г, δ, q0, Z0, F), де
Q─кінцева множина символів станів, що представляють всеможливі стани керуючого пристрою;
∑─кінцевий вхідний алфавіт;
Г─кінцевий алфавіт магазинних станів;
δ─відображення множини Q×(∑ ∪ {e})×Г у множину кінцевих підмножин множини Q×Г*;
q0 є Q─початковий стан керуючого пристрою;
Z0 є Г─символ, що знаходиться в магазині в початковий момент (початковий символ);
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.
Лему доведено. (
Еквівалентність МП-автоматів і КВ-граматик.
З допомогою отриманих результатів можна тепер показати, що мови, визначені МП-автоматами─ це загалом КВ-мови. Почнемо з побудови звичайного (недетермінованого) “низхідного” розпізнавача, еквівалентного даній контекстно-вільній граматиці.
Лема 5. Нехай G=(N, ∑, P, S)─ контекстно-вільна граматика. По граматиці G можна побудувати такий МП-автомат R, що L℮( R)= L(G).
Доведення: Побудуємо R так, щоб він моделював всі ліві виводи у G. Нехай R=({q}, ∑, N∪∑, δ, q, S, (), де δ визначається наступним чином:
якщо A→( належить P, то δ(q, ℮, A) містить (q, ();
δ(q, a, a)= {(q, ℮)} для всіх a ( ∑.
Ми хочемо показати, що:
(q,ω,A)|─n(q,℮,℮) для деяких m,n≥1 (2)
Необхідність умови доведемо індукцією по m. Припустимо, що A(m ω. Якщо m=1 і ω= a1… ak (k≥0), то:
(q, a1… ak, A) |─ (q, a1… ak, a1… ak)
|─k (q, ℮, ℮)
Тепер покладемо, що A(m ω для деякого m(1. Перший крок цього виводу повинен мати вигляд A(X1X2… Xk, де Xί(mί xί для деякого mί( m,
1 ≤ ί ≤ k, і x1x2… xk= ω.
Тоді:
(q, ω, A) |─ (q, ω, X1X2… Xk)
Якщо Xί ( N, то за припущенням індукції:
(q, xί, Xί) |─* (q, ℮, ℮)
Якщо Xί= xί ( ∑, то:
(q, xί, Xί) |─ (q, ℮, ℮)
Об’єднуючи разом ці послідовності тактів, бачимо, що:
(q, ω, A) |─+(q, ℮, ℮)
Для доведення достатності покажемо індукцією по n, що якщо
(q, ω, A) |─n (q, ℮, ℮), то A(+ ω.
Якщо n=1, то ω=℮ і A→℮ належить P. Припустимо, що твердження вірне для всіх n′(n. Тоді перший такт, зроблений МП-автоматом R, повинен мати вигляд:
(q, ω, A) |─ (q, ω, X1… Xk)
до того ж (q, xί, Xί) |─ nί (q, ℮, ℮) для 1 ≤ ί ≤ k і ω= x1x2… xk(лема 1). Тоді
A→ X1… Xk ─ правило із P, і за припущенням індукції Xί(+xί для Xί (N. Якщо
Xί (∑, то Xί(0xί. Таким чином,
A ( X1… Xk
(* x1X2… Xk
.
.
.
(* x1x2… xk-1Xk
(* x1x2… xk xk-1= ω
─ вивід стрічки ω із A у граматиці G.
Із (2), загалом, випливає, що S(+ω тоді і тільки тоді, коли
(q, ω, S) |─+(q, ℮, ℮). Отже, L℮(R)= L(G).
Лему доведено. (
Приклад 3. Побудуємо МП-автомат P, для якого L℮(P)= L(G0), де G0─ звичайна граматика, яка визначає арифметичні вирази. Нехай
P = ({q}, ∑, Г, δ, q, E, (), де δ визначається так:
(1) δ(q, ℮, E)= {(q, E+T), (q, T)};
(2) δ(q, ℮, T)= {(q, T*F), (q, F)};
(3) δ(q, ℮, F)= {(q, (E)), (q, a)};
(4) δ(q, b, b)= {(q, ℮)} для всіх b ({a, +, *, (, )}.
При вході a+a*a для P можлива серед інших послідовність тактів:
(q, a+a*a, E) |─ (q, a+a*a, E+T)
|─ (q, a+a*a, T+T)
|─ (q, a+a*a, F+T)
|─ (q, a+a*a, a+T)
|─ (q, +a*a, +T)
|─ (q, a*a, T)
|─ (q, a*a, T*F)
|─ (q, a*a, F*F)
|─ (q, a*a, a*F)
|─ (q, *a, *F)
|─ (q, a, F)
|─ (q, a, a)
|─ (q, ℮, ℮)
Зауважимо, що обчислення МП-автомата P відповідає лівому виводу стрічки a+a*a із E у контекстно-вільній граматиці G0. (
Тип синтаксичного аналізу, що проводиться для КВ-граматики МП-автоматом, побудованим у лемі 5, називається «низхідним аналізом», тому що при цьому дерево виводу будується загалом зверху(від кореня) вниз, а кожен такт виду 1 можна трактувати як передбачення чергового кроку лівого виводу.
Можна побудувати розширений МП-автомат, який працює «знизу вверх» як «висхідний аналізатор», моделюючи у зворотному порядку праві виводи у КВ-граматиці. Розглянемо стрічку a+a*a ( L(G0) і її правий вивід із E у граматиці G0:
E ( E+T( E+T*F (E+T*a ( E+F*a ( E+a*a ( T+a*a ( F+a*a ( a+a*a
Припустимо, що ми записуємо цей вивід у зворотному порядку. Якщо вважати, що перехід від стрічки a+a*a до стрічки F+a*a відбувається за правилом F→a, що застосоване «у зворотному порядку», то можна сказати, що стрічка a+a*a «згортається зліва» до стрічки F+a*a. До того ж, це єдина можлива ліва згортка. Подібним чином можна правовиводиму стрічку F+a*a згорнути зліва до стрічки T+a*a з допомогою правила T→F і так далі. Визначимо формально ліву згортку.
Означення 4: Нехай G=(N, ∑, P, S)─ контекстно-вільна граматика і
S(r* (Aω(r ((ω(r* xω ─ правий вивід у ній. Будемо говорити, що правовиводиму стрічку ((ω можна згорнути зліва(або що вона лівозгортується) до правовиводимої стрічки (Aω за допомогою правила A→(. Вказане входження стрічки ( у стрічку ((ω називається основою стрічки ((ω.
Таким чином, основа правовиводимої стрічки ─ це її будь-яка підстрічка, що являється правою частиною деякого правила, до того ж після заміни її лівою частиною цього правила також отримується правовиводима стрічка.
Приклад 4. Розглянемо граматику з правилами
S→Ac|Bd
A→ aAb|ab
B→ aBbb|abb
Вона породжує мову { an bnc|n≥1} ∪{ an b2nd|n≥1}.
Розглянемо правовиводиму стрічку aabbbbd. Єдина її основа ─ підстрічка abb, так як aBbbd ─ правовиводима стрічка. Зауважимо, що хоча ab ─ права частина правила A→ ab, вона не буде основою стрічки aabbbbd, оскільки aAbbbd ─ не правовиводима стрічка. (
Основу правовиводимої стрічки можна було б визначити і іншим способом, сказавши, що основа ─ це крона найлівішого піддерева глибиною 1 деякого дерева виводу цієї правовиводимої стрічки. (Дерево глибиною 1, що складається із вершини і її прямих потомків, що являються листям, називають кущем ).
Рис.2. Відсічення основ.
Дерево виводу ланцюжка a+a*a у граматиці G0 показано на рисунку 2. Найлівіший кущ складається із найлівішої вершини, що позначена F, і яка являється його коренем, і крони a.
Якщо видалити єдиний листок найлівішого куща, то залишиться дерево, показане на рисунку 2б. Крона F+a*a цього дерева і є результатом лівої згортки ланцюжка a+a*a, а його основа ─ крона F піддерева із корінням, позначеним T. Знову знищивши основу, отримаємо дерево, зображене на рисунку 2в.
Описаний процес згортки дерев назвемо відсічення основ.
За контекстно-вільною граматикою G можна побудувати еквівалентний розширений МП-автомат P, робота якого полягає у відсіченні основ. Тут корисно уявити собі магазин у вигляді стрічки, верхнім символом якого є найправіший, а не найлівіший символ. В силу цього домовлення конфігурації (розширеного) МП-автомата P= (Q, ∑, Г, δ, q0, Z0, F) визначається так само, як раніше, а відношення |─ трохи інакше. Якщо δ(q, a, () містить (p, (), то будемо писати (q, aω, (() |─
(p, ω, (() для всіх ω ( ∑* і ( ( Г*.
Таким чином твердження «δ(q, a, YZ) містить (p, VWX)» має різні значення в залежності від того, справа чи зліва розміщена верхня частина магазину. Якщо зліва, то верхніми символами до і після цього такту будуть Y і V, а якщо справа, то верхніми символами будуть Z і X. За даним МП-автоматом, верхній символ якого розміщений зліва, можна побудувати МП-автомат, що робить теж саме, але з верхнім символ, розміщеним справа, просто записуючи у зворотному порядку всі ланцюжки із Г*. Наприклад, якщо було (p, VWX) ( δ(q, a, YZ), то стане
(p, XWV) ( δ(q, a, ZY). Зрозуміло, що потрібно зауважити той факт, що верхній магазин знаходить тепер справа. Навпаки, МП-автомат з верхнім символом, що розміщений справа, легко перетворити у МП-автомат з верхнім символом зліва.
Ми бачимо, що означення МП-автомата у вигляді семірки можна інтерпретувати як два різних МП-автомата в залежності від того, який символ ─ правий чи лівий ─ вважається верхнім. Нам здається, що зручність означення, створеного цими двома домовленостями, перевищує можливість плутанини в початкових означеннях. Дальше, якщо не сказано протилежне, будемо вважати, що у звичайного МП-автомата верх магазину розміщений зліва, а у розширеного ─ справа.
Лема 6. Нехай G=(N, ∑, P, S)─ контекстно-вільна граматика. За G можна побудувати такий розширений МП-автомат R, що L( R)= L(G).
Роботу автомата R «розумно» розглядати як процес відсічення основ.
Доведення: Нехай R=({q, r}, ∑, N∪∑∪{$}, δ, q, $, {r}) ─ розширений МП-автомат (за нашим договором верх його магазину розміщений справа), у якому δ визначається наступним чином:
(1) δ(q, a, ℮)= {(q, a)} для всіх a ( ∑.(На таких тактах вхідні символи переносяться у магазин.)
(2) якщо A→( належить P, то δ(q, ℮, () містить (q, A);
(3) δ(q, ℮, $S)= {( r, ℮)}
Покажемо, що процес обчислення в МП-автоматі полягає у побудові правовиводимих ланцюжків граматики G, починаючи із термінального ланцюжка(на вході R) і закінчуючи ланцюжком S. Індукцією по n доведемо, що:
S(r*(Ay(rn xy веде до (q,xy,$)|─*(q,y,$(A) (3)
Базис, n=0, тривіальний: R не робить ні одного такту. Припустимо, що 3 вірна для всіх значень параметра, менших за n. Можна написати (Ay(r((y(rn-1 xy. Допустимо, що ланцюжок (( складається тільки із терміналів. Тоді ((=x і
(q, xy, $) |─* (q, y, $(() |─ (q, y, $(A).
Якщо (( ( ∑*, то можна писати ((=(Bz, де B ─ найлівіший нетермінал. За 3 із S(r* (Bzy(rn-1 xy слідує (q, xy, $) |─* (q, zy, $(B). Крім цього,
(q, zy, $(B) |─* (q, y, $(Bz) |─ (q, y, $(A) ─ також можлива послідовність тактів.
Ми заключаємо, що 3 вірна для всіх n. Так як (q, ℮, $S) |─ ( r, ℮, ℮), то
L(G) ( L( R).
Для того щоб довести зворотне включення L(R) ( L(G) і, відповідно, рівність L(G)= L( R), доведемо, що:
(q,xy,$)|─n(q,y,$(A) веде до (Ay(*xy (4)
Базис, n=0, виконується автоматично. Для перевірки кроку індукції припустимо, що 4 вірна для всіх n<m. Якщо верхній символ магазину автомата R не термінальний, то останній такт був зроблений за правилом (2) визначення функції δ. Тому можна писати:
(q, xy, $) |─m-1 (q, y, $(() |─ (q, y, $(A)
де A→( належить P. Якщо ланцюжок (( містить нетермінал, то за припущенням індукції ((y(* xy. Звідси (Ay(((y(* xy, що і стверджувалось.
В якості часткового випадку твердження 4 отримуємо, що
(q, ω, $) |─* (q, ℮, $S) веде до S(*ω. Так як R допускає ω тільки тоді, коли
(q, ω, $) |─* (q, ℮, $S) |─ (r, ℮, ℮), то звідси випливає, що L(R) ( L(G). Таким чином, L( R)= L(G).
Лему доведено. (
Зауважимо, що відразу після згортки правовиводимий ланцюжок виду (Ax представлений у R так, що (A знаходить у магазині, а x займає непрочитану частину вхідної стрічки. Після цього R може продовжувати переносити символи ланцюжка x у магазин до тих пір, поки в його верхній частині не утвориться основа. Тоді R може зробити наступну згортку. Синтаксичний аналіз цього типу називають «висхідним аналізом»(«аналізом знизу вверх») чи «аналізом згорткою».
Покажемо тепер, що мова, що визначається МП-автоматом, контекстно-вільна.
Лема 7. Нехай R=(Q, ∑, Г, δ, q0, Z0, F) ─ МП-автомат. Можна побудувати таку КВ-граматику G, що L(G)=L℮(R).
Доведення: Побудуємо G так, щоб лівий вивід ланцюжка ω в граматиці G прямо відповідав послідовності тактів, яку робить R при обробці ланцюжка ω. Нетермінальні символи будуть мати вигляд [qZr], де q, r ( Q і Z ( Г. Потім ми покажемо, що [qZr](+ω тоді і тільки тоді, коли (q, ω, Z)|─+(r, ℮, ℮).
Формально нехай G=(N, ∑, P, S), де:
N={[qZr] | q, r ( Q, Z ( Г }∪{S};
правила множини P будуються так:
(а) якщо δ(q, a, Z) містить (r, X1…Xk)(k≥1), добавимо до P всі правила виду:
[qZsk]→ a [rX1s1][s1X2s2]…[sk-1Xksk ]
для кожної послідовності s1, s2,…, sk станів із Q,
(б) якщо δ(q, a, Z) містить (r, ℮), добавимо до P правило [qZr]→ a,
(в) додамо до P правила S→[q0Z0q] для кожного q( Q.
Індукцією по m і n легко довести, що для будь-яких q, r ( Q і Z ( Г
[qZr](mω тоді і тільки тоді, коли (q, ω, Z)|─n(r, ℮, ℮).
Звідси випливає, що S([q0Z0q](+ω тоді і тільки тоді, коли
(q0, ω, Z0)|─+(q, ℮, ℮) для q( Q. Таким чином, L℮(R)= L(G).
Лему доведено. (
Результати попередніх лем і означень можна сформувати у вигляді наступної теореми.
Теорема: Твердження:
L= L(G) для КВ-граматики G,
L= L(P1) для МП-автомата P1,
L= L℮(P2) для МП-автомата P2,
L= L(P3) для розширеного МП-автомата P3
еквівалентні.
Доведення: Із (3) випливає (1) за лемою 7. Із (1) випливає (3) за лемою 5. Із (4) випливає (2) за лемою 2, а з (4) тривіально випливає (2). Із (2) випливає (3) за лемою 3, і із (3) випливає (2) за лемою 4.
Теорему доведено. (
Детерміновані МП-автомати.
Ми вже бачили, що для кожної КВ-граматики G можна побудувати МП-автомат, що розпізнає L(G). Однак побудований МП-автомат був недетермінований. В практичних застосуваннях нас більше цікавлять детерміновані МП-автомати, тобто такі, які в кожній конфігурації можуть зробити не більше одного чергово такту. В цьому розділі ми займемося детермінованими МП-автоматами і в подальшому побачимо, що, на жаль, детерміновані МП-автомати не такі потужні по своїй розпізнавальній можливості, як недетерміновані МП-автомати. Існують КВ-мови, які не можна визначити детермінованими МП-автоматами.
Мова, яка визначається детермінованим МП-автоматом, називається детермінованою контекстно-вільною мовою.
Означення 5: МП-автомат 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, ()}.
Означення детермінованого МП-автомата можна розширити, щоб включити в нього ті розширені МП-автомати, які природно вважати детермінованими.
Означення 6: Розширений МП-автомат P=(Q, ∑, Г, δ, q0, Z0, F) називається детермінованим, якщо виконані наступні умови:
# δ(q, a, () ≤1 для всіх q ( Q, a (∑∪{℮} і (( Г*;
якщо δ(q, a, ()((, δ(q, a, ()(( і (((, то жоден із ланцюжків ( і ( не є суфіксом другого(якщо верх магазину розширеного МП-автомата розміщений зліва, то тут потрібно «суфікс» замінити на «префікс».)
якщо δ(q, a, ()(( і δ(q, ℮, ()((, то жоден із ланцюжків ( і ( не являється суфіксом другого.
Легко бачити, що в тому випадку, коли розширений МП-автомат є звичайним ДМП-автоматом, це означення співпадає з попереднім. Крім того, якщо конструкція леми 2 застосовується до розширеного МП-автомату, результатом буде детермінований МП-автомат тоді і тільки тоді, коли детермінованим був вихідний розширений МП-автомат.
При моделюванні синтаксичного аналізатора бажано мати ДМП-автомат P, який зчитує всю вхідну стрічку, навіть якщо не належить мові L(P). Покажемо, що такий ДМП-автомат завжди можна знайти.
Спочатку модифікуємо ДМП-автомат так, щоб для будь-якої конфігурації, в якій частина входу залишилась непрочитаною, завжди був можливий черговий такт. Наступна лема показує, як це зробити.
Лема 8. Нехай 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).
Лему доведено. (
ДМП-автомат може, виходячи із певної конфігурації, зробити безкінечне число ℮-тактів, не прочитавши більше ні одного вхідного символу. Таку конфігурацію ми назвемо зациклюючою.
Означення 7: Конфігурація (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. Зауважимо, ( може бути ℮.
(2) Якщо (q, ℮, A) ─ зациклюючи конфігурація, з’ясувати, чи існує таке r(F, що (q, ℮, A) |─ j (r, ℮, () для деякого 0( j( n3. При цьому знову використовується пряме моделювання. Якщо так, то включити (q, A) в C2. В противному випадку включити (q, A) в C1. Ми стверджуємо, що якщо P досягнути заключної конфігурації, виходячи із (q, ℮, A), то це повинно статися за n3 або менше число тактів. (
Теорема 2. Алгоритм 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′ повинні двічі зустрічатись в якості поточного стану і верхнього символу магазину; іншими словами, можна писат...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора