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


 

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

80969. Особливості пізнавального інтересу учнів до історії 35.74 KB
  Метою розвитку мотиваційної сфери учнів у навчанні історії виступає формування стійкого інтересу до предмета що передбачає активне емоційнопізнавальне ставлення школярів до досліджуваних історичних подій до зясування їхніх причин і наслідків а також до оволодіння вміннями необхідними для всебічного вивчення минулоі о і сучасності на основі різноманітних джерел. Отже одним із важливих завдань навчання в умовах цілісної методичної системи є підвищення рівня розвитку інтересу. У числі загальних зовнішніх причин падіння інтересу...
80970. Організація самостійної роботи учнів при вивченні теми: «Виникнення та розвиток Київської Русі » (7 клас) 39.16 KB
  Проблема диференційованого підходу до учнів у навчанні історії. Диференційоване навчання організація навчальновиховного процесу з урахуванням типових індивідуальних особливостей учнів. Складнішим і ефективнішим видом диференційованого навчання є здійснення його в умовах поділу класу на групи залежно від рівня навчальних можливостей учнів.
80971. Планування роботи із контурною картою при вивченні теми: «Великі географічні відкриття: зустріч цивілізацій» (8 клас) 37.85 KB
  Розглядаючи тему: Великі географічні відкриття доба відкриттів європейськими мореплавцями невідомих раніше морів та океанів островів і континентів здійснення першої навколосвітньої морської подорожі колонізації заморських територій кінець XVсеред. Нові географічні відкриття зумовлювалися насамперед бурхливим розвитком продуктивних сил прагненням європейців задовольнити зрослі потреби в дорогоцінних металах і прянощах відповідно пошуками морських шляхів до Китаю та Індії. Великі географічні відкриття стали можливими завдяки значному...
80972. Способи вивчення пізнавального інтересу учнів до історії 38.89 KB
  В учнівських диктантах було відтворено від 8 до 21 інформаційних одиниць. Діагностуючий диктант допомагає вчителю вчасно звернути увагу на труднощі в сприйнятті й осмисленні історичного матеріалу що є в учнів даного класу 9віку0. Якщо взяти за основу зміни особистісних особливостей учнів то в своїй роботі у напрямку посилення пізнавального інтересу учнів до історії перш за все беру до уваги що учні основної школи та старшої школи мають зовсім різну підготовки виходячи з їх віку.
80973. Дайте оцінку сучасним вимогам до уроків історії 39.52 KB
  Розуміння і виконання вчителем сучасних вимог до уроку які визначаються соціальним замовленням. Оптимального балансу в змісті уроку компонентів світової національної регіональної та локальної історії. Творчою емоційної атмосфери заснованої на інтерес учнів до змісту уроку та видами навчальної роботи...
80974. Визначення рівня розвитку пізнавальних здібностей школярів до вивчення історії 32.33 KB
  Наприклад: 1 Складіть максимальну кількість речень з одними і тими самими словами але різних за смислом: лицаріхрестоносці кривава битва князівські дружини діагностика вербальної уяви.Порівняйте два зображення на історичну тему і знайдіть відмінності діагностика довільної уваги. По деталі здогадайтеся що це за споруда і назвіть її діагностика образної уяви. На основі аналітичного опису намалюйте предмет про який іде мова діагностика репродуктивної та творчої уяви.
80975. Права та обов’язки вчителя історії 36.39 KB
  Мають право на: захист професійної честі гідності; участь в обговоренні та вирішенні питань організації навчальновиховного процесу; проведення науководослідної експериментальної пошукової роботи відповідно до діючих нормативних документів; вільний вибір форм методів засобів навчання виявлення педагогічної ініціативи; дострокову атестацію на отримання відповідної категорії і педагогічного звання; соціальне і матеріальне забезпечення відповідно до законодавства; підвищення кваліфікації перепідготовку вільний вибір змісту...
80976. Проблема методів навчання історії та їх класифікація 36.03 KB
  Провідні поняття повязані з процесом навчання історії стали предметом наукового інтересу в дискусіях радянських методистів у 5070ті pp. В обговоренні проблеми свої варіанти класифікації методів навчання історії в різні роки запропонували всі провідні вчені однак вони так і не прийшли до єдиної думки. Тому в сучасній методичній літературі збереглася різноманітність підходів до визначення понять методи прийоми способи навчання різні підстави їх систематизації і деяка суперечливість у вживанні методичних термінів у спеціальній...
80977. Дайте загальну характеристику історичних карт 37.4 KB
  Історичні карти карти що відображують історичні явища і події взаємозвязки суспільних явищ минулого з географічними чинниками показують розміщення древніх культур держав соціальні рухи торгівельні дороги пересування людей військові удари на карті показують стрілками місця боїв схрещеними мечами райони повстань крапками або вогнищами. Історичні карти створюються на географічній основі і є математично визначеним зменшеним узагальненим образнознаковим зображенням історичних подій явищ процесів чи періодів...