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,  називається  "низхідним  аналізом",  або  аналізом  "зверху униз", чи прогнозуючим. Під час такого аналізу дерево виводу  будується, починаючи з кореня, у напрямку зверху униз, і кожний такт  можна трактувати як передвіщення чергового кроку лівого виводу.


 

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

36125. Релігієзнавство. Основи філософських знань 181 KB
  Філософія релігії Мені довелося потіснити знання щоб звільнити місце вірі І. Центральний об’єкт релігійної віри – Бог саме з нього виводиться зміст усієї релігії. Розподіл філософії та релігії на самостійні форми суспільної свідомості відбувається лише в Новий час коли починають розвиватися природничі науки механіка. Філософія прагне заповнити емоційнодушевну пустоту відновити властиву релігії психологічну рівновагу.
36126. Основи національної економіки 2.85 MB
  Основні етапи розвитку національної економіки України. Особливості й ключові завдання сучасного етапу розвитку української національної економіки. Основні показники рівня розвитку національної економіки. ПОНЯТТЯ НАЦІОНАЛЬНОЇ ЕКОНОМІКИ ЯК РЕЗУЛЬТАТУ ЕКОНОМІЧНОЇ ДІЯЛЬНОСТІ Поняття національна економіка досить багатозначне оскільки це перш за все певний підсумок багатовікового розвитку народногосподарського комплексу країни.
36127. Соціальне страхування 462.5 KB
  Сутність принципи й роль соціального страхування План Сутність і необхідність соціального страхування в умовах ринкової економіки. Становлення і розвиток соціального страхування. Сутність і необхідність соціального страхування в умовах ринкової економіки. У багатьох країнах діє система взаємодоповнюючого соціального страхування що містить у собі такі елементи як: Державне соціальне забезпечення; Корпоративні соціальні програми; Індивідуальне часткове страхування.
36128. Системне програмне забезпечення 506.5 KB
  Переміщаючі завантажувачі можуть помістити програму в будьяке вільне місце в памяті. Очевидно що в більшості випадків початкові дані потрапляють в оперативну память із зовнішніх пристроїв. Класифікація ресурсів При розробці перших систем ресурсами вважалися процесорний час память канали вводу виводу і периферійні пристрої. Відповідно доки здійснювався обмін даними між оперативною памяттю і зовнішніми пристроями процесор не міг виконувати обчислення.
36129. КОНСПЕКТ ЛЕКЦІЙ НАВЧАЛЬНОЇ ДИСЦИПЛІНИ ЕКОЛОГІЧНА СТАНДАРТИЗАЦІЯ І СЕРТИФІКАЦІЯ для студентів 5 курс 130 KB
  Національні стандарти мають позначку абревіатуру ДСТУ – державний стандарт України. Міжнародні стандарти що введені в дію в Україні мають позначки ДСТУ ISO і ДСТУ EN. Розроблені державні стандарти України отримали абревіатуру – ДСТУ. З’явилися екологічні стандарти з позначками: ДСТУ ISO ДСТУ EN.
36130. СТАТИСТИКА. Лекційні заняття 1.67 MB
  Ознака яка набуває в межах сукупності різних значень називається варіюючою змінною мінливою а відмінність коливання ознаки варіацією. Наприклад ознаки людини: вік стать сімейний стан освіта тощо; ознаки підприємства: спеціалізація форма власності рентабельність виробництва і т. За характером вираження ознаки поділяють: Атрибутивні – ознаки окремі значення яких виражаються словами. Кількісні – ознаки окремі значення яких виражаються числами вік людини розряд робітника стаж роботи і вони відіграють головну роль в статистиці.
36131. Соціальна робота та соціальні технології 1003.5 KB
  Специфіка технологій соціальної роботи. Критерії ефективності процесу технологізації соціальної роботи. Державноправові засади соціальної роботи. Основні нормативні акти щодо питань соціальної роботи.
36132. Бухгалтерський облік 978.5 KB
  Вимірники часу праці дні години хвилини людинодні людиногодини Використовують з метою обліку кількості відпрацьованого часу та обліку праці витраченої на виготовлення продукції. Звіт про фінансовий стан підприємства який відображає на певну дату його активи зобов'язання і власний капітал відповідно до ПСБО 1 Загальні вимоги до фінансової звітності Спосіб економічного групування та узагальненого відображення у грошовій оцінці стану господарських засобів і джерел їх утворення на певну дату Визначення балансу як форми...
36133. Склад і структура видатків державного бюджету України 507.5 KB
  Капітальні вкладення і джерела їх фінансування. Бюджетне фінансування економіки за рахунок цільових державних позик. Організація наукових досліджень і джерела їх фінансування. Фінансування фундаментальних досліджень у наукових установах Національної академії наук України у відомчих наукових закладах та вищих навчальних закладах.