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


 

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

55392. Проектная деятельность на уроке технологии 86 KB
  Обобщить знания о пищевом рационе режиме питания условиях приёма пищи и сформулировать правила рационального питания. Воспитывать бережное отношение к здоровью и продуктам питания.
55393. Метод проектов на уроках истории и во внеклассной деятельности 396 KB
  Материально-техническое обеспечение проекта: аудио видео стенд. Для подготовки учеников к настоящим проектам необходимо начать их знакомство с данной технологией на уровне второй ступени обучения.
55394. Використання проектної технології як засіб активізації пізнавальної діяльності учнів на уроках інформатики 339.5 KB
  Мій досвід роботи в школі показав що в розвитку зацікавленості до предмета не можна покладатися тільки на зміст виучуваного матеріалу уникаючи залучення учня до активної діяльності.
55395. Творчі проекти у початковій школі 44 KB
  Творчий проект Казка про народнопоетичні символи України Я і Україна 4 клас Мета проекту. Поглибити знання школярів про народнопоетичні символи України; розвивати творчу уяву зв’язне мовлення школярів; виховувати любов до Батьківщини. Учні ознайомлюються з народнопоетичними символами України; виконують завдання у групах Казкарі та Художники. Завдання Групі казкарів: скласти казки про рослинні та тваринні народнопоетичні символи України: вербу калину тополю соняшник соловейка лелеку та ін.
55396. У пошуках майбутньої професії 63 KB
  Мета: познайомити учнів з деякими професіями, стимулювати стійкий інтерес до здобуття професійних знань;розвивати ерудицію, кмітливість, винахідливість , артистизм, навики ділової гри; формувати свідоме ставлення до вибору професії.
55397. Проект по профориентации 467.5 KB
  С этого момента начинается работа над проектами. Каждый ребёнок получил задание в результате выполнения которого он должен прийти к выводу почему именно эта профессия ему нравится.
55398. МИР ПРОФЕССИЙ 241.5 KB
  Познакомить обучающихся с престижными редкими и новыми профессиями охарактеризовать предмет труда каждой профессии. Воспитывать житейское отношение к выбору профессии.
55399. Вибір майбутньої професії 145 KB
  У цьому випадку людина вивчає власні можливості інтереси здібності переглядає багато професій і свідомо обирає ту яка підходить саме для неї з урахуванням сучасних проблем суспільства та особливостей ринку праці.
55400. Пишаюся своєю професією 167 KB
  Метою даної методичної розробки є удосконалення досвіду проведення поззаудиторних заходів. На сучасному етапі перед професійною освітою багато завдань, але найголовніше – виховувати гідних громадян...