68839

Автомати з магазинною пам’яттю

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-26

132 KB

8 чел.

Лекція 9
Автомати з
магазинною пам’яттю

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

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

Автомат з магазинною пам’яттю

Формальне означення автомату магазинного типу

Формально автомат магазинного типу визначається як шістка

R = (Q, , Γ, , q0, Z0 ),

де Q - скінчена множина станів керуючого пристрою;  - скінчений  вхідний алфавіт; Γ - скінчений алфавіт магазинних символів; - функція переходів, що є таким відображенням 

       : Q x (  {}) х Γ  (Q х Γ*), де 

(Q х  *) - множина підмножин прямого добутку  Q  та  Γ * ; q0  Q  -  початковий стан керуючого пристрою; Z0  Γ - символ, що знаходиться у магазині у початковий момент (початковий символ).

    Означення  9.1.  Конфігурацією   МП-автомату   R    називається  трійка 

(q, w, )  Q х * х Γ * , 

де  q - поточний стан керуючого пристрою;  w - непрочитана частина вхідного рядка; перший символ рядка   w   знаходиться  під  головкою  читання; якщо  w = , вважають, що весь вхідний рядок прочитаний;  - вміст магазину; найлівіший символ рядка -  це  верхній  символ  магазину; у випадку   = , вважають, що магазин пустий.  

       Такт (крок)   роботи    МП-автомату  R  будемо уявляти як бінарне  відношення    на множині конфігурацій. Будемо писати  (q, av, z) (q, v, γ),

якщо  (q, γ)  (q, a, z),  де   q, q  Q,  a    {},  v  *,  z  Γ,  , γ  Γ *.

Аргументи  функції   утворюють трійку (q, a, z), що  називається поверхневою конфігурацією автомату.  

    Якщо  а  , то у поданому  такті   МП-автомат, маючи керуючий пристрій у стані  q, символ  а  під  головкою  читання  та   z   у  вершині стеку, змінює стан керуючого пристрою на q, зсовує вхідну головку на одну комірку  праворуч  і  замінює  верхній  символ  стеку рядком  γ  магазинних символів. При γ =  верхній  символ  просто вилучається.

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

 Звичайним  чином   визначаються   відношення  i для   усіх  невід’ємних цілих  і,  * та  +.

Початковою   конфігурацією    МП-автомату  R  називається  конфігурація вигляду  (q0, w, Z0),  де  w  *.

Заключна  конфігурація - це  конфігурація  вигляду  (q, , ),  де  q  Q.  

Означення 9.2. Кажуть, що рядок  w   приймається   МП-автоматом  R, якщо  (q0, w, Z0) * (q, , ).  

Означення 9.3. МП-автомат  R представляє мову  L(R), коли  L(R)  є  множиною усіх рядків, що приймаються автоматом  R.  

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

Приклади  МП-автоматів

Розглянемо приклади  МП-автоматів.

Приклад 1. Нехай подано мову  L1 = {0n1n | n  0}. Тоді автомат  R1, що представляє мову  L1, має вигляд

R1 = ({q0, q1}, {0, 1}, {S, 0}, , q0, S), 

де 

  1.   (q0, 0, S)  = {(q0, 0)},

                                                2)   (q0, 0, 0) = {(q0, 00)},  

                                                     3)   (q0, 1, 0) = {(q1, )},  

                                                4)   (q1, 1, 0) = {(q1, )}. 

Припустимо, що на вхід надходить рядок  0011. Тоді

           (q0, 0011, S) (q0, 011, 0) (q0, 11, 00) (q1, 1, 0) (q1, , ). 

Отже, рядок приймається. Коли на вхід надходить  0101, маємо

(q0, 0101, S) (q0, 101, 0) (q1, 01, ).

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

Приклад 2. Подано мову  L2 = {wwr | w  (a, b}+},

де  wr  - рядок, що складається з  символів  рядка  w, записаних  у  зворотному  порядку, тобто якщо  w = s1 s2 … sk,  то  wr =  sk sk-1 … s1. МП-автомат, що прдставляє цю мову, можна уявити у вигляді

R2 = ({ q0, q1}, {a, b}, {S, a, b}, , q0, S ),

 де 

                                               1) (q0, a, S) = {( q0, a)},

                                               2) (q0, b, S) = {(q0, b)},

                                          3) (q0, a, a) = {(q0, aa), (q1, )},  

                                          4) (q0, a, b) = {(q0, ab)},

                                          5) (q0, b, a) = {(q0, ba)}, 

                                          6) (q0, b, b) = {(q0, bb), (q1, )},

                                          7) (q1, a, a) = {(q1, )},

                                          8) (q1, b, b) = {(q1, )}.

Роботу  МП-автомату R2 можна уявити таким чином. Спочатку R2 створює у магазині копію деякої частини вхідного рядка за  правилами  1), 2), 4) та 5) і першими альтернативами правил 3), 6). Кожного разу,  коли наступний вхідний символ співпадає з попереднім, створюється додатковий екземпляр автомату, який  починає  порівнювати  прочитану  частину вхідного рядка з наступною. Створенню додаткового екземпляра  автомату  відповідає  друга  альтернатива  правила  3),  або  6), а порівняння виконується за правилами 7) та 8). Якщо деякий додатковий екземпляр автомату виявляє розбіжність символів, то він "вмирає". Інші  продовжують працювати. Якщо після закінчення читання вхідного  рядка  у деякому екземплярі автомату виявляється пустий стек, то цей рядок приймається автоматом.

Легко бачити, що коли  w = s1 s2 ... sn sn sn-1 ... s1,  де  si {a, b},  1  i  n,             то  (q0, w, S)) n (q0, sn, sn-1, … , s1, sn sn-1 ... s1)     (q1, sn-1, sn-2, … , s1, sn-1 sn-2 ... s1) n-1(q1, , ). 

Таким чином,  L2  L(R2). Можна показати, що і  L(R2)  L2. Тому L2 = L(R2).

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

Зв’язок між  МП-автоматами і  КВ-граматиками

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

Лема 9.1. Нехай  R = (Q,    ,    , , q0, Z0)  - МП-автомат. Якщо 

(q, w, A) n (q, , ),  

то

(q, w, A) n (q, , ),   A  Γ,    Γ*. 

 Доведення. Скористаємося індукцією за n. Для  n = 1 твердження  очевидне,  оскільки крок  МП-автомату визначається поверхневою конфігурацією. Припустимо, що лема вірна для усіх   n  таких, що  1  n <  k,  і  нехай

(q, w, A) k (q, , ),

Тоді оскільки у кожному такті зі стеку може вилучатися не більше одного (верхнього) символу, відповідна послідовність тактів повинна  мати вигляд

(q, w, A) (q1,  w1,  X1 X2 … Xm) N1(q2,  w2,  X2 X3 … Xm) N2 Nm-1(qm,  wm, Xm) Nm(q, , ),  де  m  1  і   Ni <  k   i | 1 i m.

Внаслідок цього для будь-якого    Γ*  можлива послідовність  

(q, w, A) (q1,  w1,  X1 X2 … Xm) N1(q2,  w2,  X2 X3 … Xm) N2Nm-1

(qm,  wm, Xm) Nm(q, , ).  

Тут у кожному такті, крім першого, використано припущення індукції, а у першому застосовано  те  ж саме  правило, що і  у  попередній  послідовності.

Теорема 9.1. Для кожної  КВ-граматики  G = (N, T, P, S)  існує  такий  МП-автомат  R, що  L(R) = L(G).

Доведення. Побудуємо  R так, щоб він моделював усі ліві виводи у  G. Візьмемо  R = ({q}, T  {}, N  T, , q, S),  де    визначається таким чином:

1) якщо  A    P,    то  (q , )  (q, , A); 

2)   (q, a, a) = {(q, )},   a T.

Покажемо, що

А + w  (q, w, A) + (q, , )                     (9.1) 

Достатність умови доведемо індукцією за числом кроків виводу m. Припустимо,  А  m w. Якщо  m = 1, і  w = а0а1 ...аk  (k  0),  аi  T, i = 1,k , а0 = , то

(q, а0а1 ...аk, A) (q, а1 ...аk, а1 ...аk) k (q, , ).

Тепер припустимо, що  m > 1. Перший крок виводу  А m w  повинен  мати вигляд   А Х1 Х2 ...Хt,  де   Xi  Mi wi  для деякого  Mi < m,  1  i  t,  w1 w2 wt = w,  wi  *. Тоді  (q, w, A) (q, w, Х1 Х2 ...Хt).  

Якщо  Хi  N, то за припущенням індукції   (q, wi, Xi)    + (q, , ).                 

Якщо  Хi  = аj  , то  (q, аj, Xi) (q, , ).  

Об’єднуючи послідовності тактів для усіх  і, з урахуванням леми  9.1 одержуємо   (q, w, A) + (q, , ).                    

Для доведення необхідності покажемо за допомогою індукції за m, що коли   (q, w, A) m (q, , ),  то  А + w.                              

Якщо  m = 1, то з правил побудови    прямує, що  w = , і  А     Р. Припустимо, що твердження вірне для усіх  m  таких, що  1  m < k,   і  

(q, w, A) k (q, , ).

Тоді перший такт, зроблений  МП-автоматом  R, повинен мати вигляд 

(q, w, A) (q, w, Х1 Х2 ...Хt ),

причому  (q, wi, Хi) Mi (q, , )   для усіх  1 і  t, w = w1 w2wt,  wi  * (на підставі леми  9.1).  Це означає, що  А Х1 Х2 ...Хt  Р, і за  припущенням індукції  Хi + wi   для  Хi   N. Якщо  Хi  , то  Хi 0 wi . Таким чином, одержуємо  А Х1 Х2 ...Хt * w1 Х2 ...Хt  *    ...  * w1 ... wt-1Хt  w1 ... wt-1wt =  w  -  вивід рядка  w  з  А  у граматиці  G.

З  (9.1)  випливає, що  S  + w  тоді і тільки тоді, коли (q, w, S) + (q, , ).                  

Отже  L(R) = L(G).

Розглянемо як приклад  МП-автомат  R0,  для якого  L(R0) = L(G0), де G0 - граматика арифметичних виразів:  G0  = ( {E, T, F}, {a, (, ), +, *}, P, E), і  Р  складається з продукцій

1. Е   Е + Т | Е

                                                          2. T T * F | F

                                                          3. А  (E) | x

MП-автомат  R0  можна уявити у вигляді

R0  = ({q}, {x, +, *, (, )}, {E, T, F, x, +, *, (, )}, , q, E),

де     визначається таким чином

            1) (q, , E) = { (q, E+T), (q, T) };

            2) (q, , E) = { (q, T*F), (q, F) };

            3) (q, , E) = { (q, (E)), (q, a) };

            4) (q, a, a) = { (q, ) }, a {x, +, *, (, ) }.

При вході  x + x * x  для  R0  серед  інших  можлива  така  послідовність тактів   (q, x+x*x, E) (q, x+x*x, Е+T) (q, x+x*x, T+T) (q, x+x*x, F+T)       (q, x+x*x, x+T) (q, +x*x, +T) (q, x*x, T) (q, x*x, T*F) (q, x*x, F*F)  

(q, x*x, x*F) (q, *x, *F) (q, x, F) (q, x, x) (q, , ).

Як бачимо, робота  МП-автомату  R0  відповідає  лівому  виводу  рядка  x + x * x  з  символу  Е  у  КВ-граматиці G0.

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


 

А также другие работы, которые могут Вас заинтересовать

80326. ТЕХНІКА І ФОРМИ БУХГАЛТЕРСЬКОГО ОБЛІКУ 166.24 KB
  Облікові регістри — це носії спеціального формату (паперові, мащинні) у вигляді відомостей, журналів, книг, журналів-ордерів тощо, призначені для хронологічного, систематичного або комбінованого накопичення, групування та узагальнення інформації з первинних документів, що прийняті до обліку.
80327. БУХГАЛТЕРСЬКА (ФІНАНСОВА) ЗВІТНІСТЬ 178.03 KB
  Поняття та принципи побудови звітності Бухгалтерський облік як відомо це процес виявлення вимірювання реєстрації накопичення узагальнення зберігання та передачі інформації про діяльність підприємства користувачам для прийняття рішень. Підсумкове узагальнення інформації та одержання підсумкових показників що характеризують діяльність підприємства здійснюється шляхом складання звітності за звітний період. Баланс підприємства складається станом на кінець останнього дня кварталу або року. Перший звітний період новоствореного...
80328. ЗАГАЛЬНА ХАРАКТЕРИСТИКА І СУТЬ БУХГАЛТЕРСЬКОГО ОБЛІКУ 63.5 KB
  Оперативно-технічний облік являє собою збір поточної інформації про хід господарської діяльності підприємства, а також контроль за здійсненням окремих операцій безпосередньо в період їх виконання.
80329. ПРЕДМЕТ І МЕТОД БУХГАЛТЕРСЬКОГО ОБЛІКУ 80.5 KB
  Виходячи із цього джерела утворення господарських засобів теж є одним із елементів предмету бухгалтерського обліку. Зазначені господарські операції відображають процес кругообігу господарських засобів підприємства. Джерела утворення господарських засобів які дають відповідь на питання за рахунок чого сформовано господарські засоби. До засобів праці належать земельні ділянки будівлі і споруди машини і обладнання транспортні засоби та ін.
80330. Бухгалтерський баланс. Зміни в балансі, зумовлені господарськими операціями 136 KB
  Бухгалтерський баланс Бухгалтерський баланс його зміст і будова Форма структура і зміст балансу Зміни в балансі зумовлені господарськими операціями Бухгалтерський баланс його зміст і будова Для забезпечення оперативного керівництва діяльністю підприємства необхідна достовірна інформація про наявні у господарстві ресурси їхній склад і розміщення а також про джерела їх формування і цільове призначення. Таку інформацію узагальнену і згруповану у відповідному порядку одержують за допомогою бухгалтерського балансу. У лівій частині...
80331. Економічна ефективність сільськогосподарського виробництва 106.5 KB
  Все ж наближено про досягнутий рівень соціальної ефективності можна судити за таким узагальнюючим показником визначеним у динаміці як питома вага прибутку спрямованого на соціальні доходи у загальній масі чистого прибутку а також величина цього прибутку на одного середньооблікового працівника. Для оцінки рівня екологічної ефективності можуть бути використані такі показники: – частка чистого прибутку підприємства що направляється на заходи екологічного спрямування і його абсолютна величина в динаміці; – частка сільськогосподарської...
80332. Земельні ресурси та ефективність їх використання 145.5 KB
  Земля - головна умова існування людського суспільства і найважливіше джерело національного багатства, найперша передумова і природна основа суспільного виробництва, універсальний фактор будь-якої діяльності людини.
80333. Матеріально-технічна база в сільському господарстві 44.52 KB
  Машинотракторний парк та ефективність його використання. Транспортні засоби та ефективність їх використання. Це потребує додаткових витрат і впливає на ефективність використання матеріальнотехнічних засобів. Останні визначаються ростом і розвитком живих організмів і суттєво впливають на ефективність використання всіх інших засобів виробництва.
80334. Основні фонди та оборотні засоби сільськогосподарського підприємства 148 KB
  Амортизація основних фондів підприємства. Показники використання основних виробничих фондів підприємства. При цьому засоби праці знаходять своє вираження в основних фондах підприємства а предмети праці – в оборотних фондах. До основних виробничих фондів належать такі фонди які беруть безпосередню участь у процесі виробництва і формуванні собівартості продукції.