68839

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

Лекция

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

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

Украинкский

2014-09-26

132 KB

10 чел.

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


 

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

80360. ЗАСАДИ КРИМІНАЛЬНОГО ПРОЦЕСУ 92.37 KB
  Поняття, значення і класифікація засад кримінального провадження. Конституційні засади кримінального провадження. Спеціальні засади кримінального провадження та їх характеристика.
80361. Фіксація ходу і результатів негласних слідчих дій 31.9 KB
  Фіксація ходу і результатів негласних слідчих дій. Поняття фіксації негласних слідчих розшукових дій Згідно з КПК України слідчий має право негласно виявляти та фіксувати сліди тяжкого злочину документи та інші предмети що можуть бути доказами про злочин чи особу яка його вчинила. Негласне виявлення та фіксування слідів тяжкого злочину полягає у здійсненні працівником міліції комплексу негласних слідчих розшукових дій для безпосереднього пізнання і сприймання властивостей стану характерних ознак і звязків обєктів матеріального...
80362. Зняття інформації з транспортних телекомунікаційних мереж 37.48 KB
  Зняття інформації з транспортних телекомунікаційних мереж. Організаційноправові засади зняття інформації з транспортних телекомунікаційних мереж Зняття інформації з транспортних телекомунікаційних мереж мереж що забезпечують передавання знаків сигналів письмового тексту зображень та звуків або повідомлень будьякого виду між підключеними до неї телекомунікаційними мережами доступу є різновидом втручання у приватне спілкування яке проводиться без відома осіб які використовують засоби телекомунікації для передавання інформації на...
80363. АРХІТЕКТУРА ТЕАМ FOUNDATION SERVER 237 KB
  У TFS використана логічна трирівнева архітектура, що розділяється на клієнтський рівень, а також рівні додатків і даних. Клієнти TFS взаємодіють з рівнем додатків за допомогою різних веб-cлужб. У свою чергу, рівень додатків підтримується різними базами даних на рівні даних.
80364. ДОКАЗИ І ДОКАЗУВАННЯ У КРИМІНАЛЬНОМУ ПРОЦЕСІ 94.66 KB
  Доказування і сучасна модель кримінального судочинства М. ВСТУП Завданнями кримінального судочинства є захист особи суспільства та держави від кримінальних правопорушень охорона прав та законних інтересів учасників кримінального провадження а також забезпечення швидкого повного та неупередженого розслідування з тим щоб кожний хто вчинив кримінальне правопорушення був притягнутий до відповідальності в міру своєї вини жоден невинуватий не був обвинувачений або засуджений і жодна особа не була...
80365. Зняття інформації з електронних інформаційних систем 35.82 KB
  Зняття інформації з електронних інформаційних систем. Зміст поняття та правові засади негласної слідчої розшукової дії зняття інформації з електронних інформаційних систем. Прийнятий КПК змінює процесу здобування інформації негласним шляхом. Зокрема втручання в приватне спілкування є: аудіо та або відеоконтроль особи; арешт огляд і виїмка кореспонденції; зняття інформації з телекомунікаційних мереж; зняття інформації з електронних інформаційних систем.
80367. Капітал: процес виробництва і нагромадження. Наймана праця і заробітна плата 133 KB
  Наймана праця і заробітна плата Вступ до теми Сучасна економічна наука трактує капітал як складну багатоаспектну категорію еволюція якої відобразила історичний процес розвитку природи форм руху динаміки та структури товарного виробництва. Метою сьогоднішнього заняття є дослідити капітал як економічну категорію первісне нагромадження капіталу перетворення грошей у капітал. Капітал як економічна категорія.
80368. Витрати виробництва і прибуток 134 KB
  Витрати виробництва і прибуток Вступ до теми Актуальність Метою сьогоднішнього заняття є дослідити суть та економічне значення витрат класифікацію витрат прибуток як економічна категорія види прибутку. У процесі виробництва здійснюються витрати ресурсів більшість яких купується на ринках і має вартісну форму. Тому витрати це не просто витрати а витрати ресурсів що набувають на ринку вартісної форми. Поперше з точки зору всього суспільного виробництва витрати виробництва поділяються на витрати суспільства і витрати його первинних...