Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Автомати з магазинною пам’яттю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2006
Тип роботи:
Курсова робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Інститут прикладної математики та фундаментальних наук
Кафедра прикладної математики
Курсова робота
на тему:
„Автомати з магазинною пам’яттю”
Виконала:ст.гр. ПМ–32
Перевірила: Тесак І.Є.
Львів 2006 Вступ
У роботі розглядатимуться положення пов’язані з функціонуванням автоматів з магазинною пам’яттю, їхні види, побудова тощо.
Скінченні автомати можуть вирішувати лише ті завдання, які вимагають скінченого об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок: кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має свою „роль”, тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною.
Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам’ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазина (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна вносити у магазин і видаляти їх з нього по одному. При цьому видаляється завжди лише верхній символ, тобто символ, який був внесений у магазин останнім.
Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (МП–автомат). У ньому дуже просто поєднується пам’ять скінченого автомата і магазинна пам’ять.
Як і у випадку скінченого автомата, обробка скінченого ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок:
переходу у новий стан;
заштовхування символу в магазин;
виштовхування символу з магазина;
зчитування символу зі вхідного ланцюжка.
Отже, наведено достатньо фактів, які підтверджують актуальність опрацювання питання про автомати з магазинною пам’яттю.
Базові означення МП–автоматів
Означення МП–автомата. Принцип роботи. Приклади.
Автомати з магазинною пам’яттю відомі також як МП–автомати.
Магазинний автомат – це зазвичай скінченний автомат, який називають керуючим, в якого, крім вхідного і вихідного каналів, є ще канал для роботи з магазином. Магазин являє собою пам'ять, яка має назву магазинної пам'яті, де може зберігається одне слово в деякому алфавіті. Цей алфавіт називається магазинним алфавітом і, взагалі кажучи, може відрізнятися від вхідного і вихідного алфавітів автомата. Магазин зручно зображати у вигляді послідовності чарунок пам’яті, перенумерованих числами натурального ряду і розміщених по вертикалі таким чином, що перша чарунка завжди стає верхньою. Слово із EMBED Equation.DSMT4 символів магазинного алфавіту EMBED Equation.DSMT4 розміщається у верхніх EMBED Equation.DSMT4 чарунках магазину, а решта заповнюється спеціальним порожнім символом, відмінним від символів алфавіту EMBED Equation.DSMT4 . Магазин може працювати в двох режимах: читання і запису. При читанні сприймається буква, що знаходиться в чарунці. При цьому буква витирається з цієї чарунки, а частина слова, що залишається в магазині, зміщується на одну чарунку вверх. В режимі запису, навпаки, слово, що зберігається в магазині, зміщується вниз на одну чарунку, а в чарунку, яка при цьому звільнилася, записується відповідний символ.
Означення. МП–автомат – це така сімка EMBED Equation.DSMT4 , де:
EMBED Equation.DSMT4 – скінчена множина станів
EMBED Equation.DSMT4 – скінчений вхідний алфавіт
EMBED Equation.DSMT4 – скінчений алфавіт магазинних станів
EMBED Equation.DSMT4 – функція переходів і виходів, яка відображає елементи декартового добутку EMBED Equation.DSMT4
EMBED Equation.DSMT4 – початковий стан
EMBED Equation.DSMT4 – символ, який знаходиться в магазині в початковий момент (початковий символ)
EMBED Equation.DSMT4 – множина кінцевих станів.
На кожному кроці роботи МП–автомат може або занести щось в магазин, або взяти якесь значення з його вершини. Відмітимо, що МП–атомат може продовжувати працювати в випадку порожнього, звільненого магазину.
МП–автомат схожий до скінченного автомата, але відрізняється від останнього робочою пам’яттю – магазином, в який записуються символи із ще одного алфавіту – алфавіту магазинних символів. Кожний рух МП–автомата визначається в залежності від поточного стану управління, вхідного символу або незалежно від нього – так звані рухи від верхнього символу магазину. Один рух магазинного автомата означає заміщення верхнього символу магазину деяким магазинним ланцюжком, зазвичай порожнім (стирання верхнього символу магазину), і перехід в новий стан управління. При цьому поточним вхідним символом стає наступний символ вхідного ланцюжка, якщо виконується рух, залежний від вхідного символу або поточний вхідний символ залишається тим самим, якщо виконується такт. Оскільки такт залежить від верхнього символу магазину, то з самого початку в магазині знаходиться один символ – початковий символ магазину.
З точки зору абстрактної теорії автоматів станами магазинного автомату потрібно було б вважати пари EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 , EMBED Equation.DSMT4 –слово, що записане в магазині. Оскільки множина слів в алфавіті EMBED Equation.DSMT4 нескінченна, то і магазинні автомати – теж нескінченні. Надалі станом магазинного автомата будемо вважати стан керуючого автомата, а слово EMBED Equation.DSMT4 – станом магазину.
Вважається, що деякий ланцюжок прийнятий, якщо магазинний автомат з початкового стану управління, маючи в магазині єдиний – початковий символ магазину і прочитавши даний ланцюжок на вході, переходить в один із своїх кінцевих станів або звільняє магазин. Кожен конкретний МП–автомат використовує тільки одну з цих двох ознак сприйняття вхідного ланцюжка.
Означення. МП–автомат називається МП–розпізнавачем, якщо у нього є дві можливості – допустити і не допустити.
Означення. Конфігурацією МП–автомата називається трійка EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 – поточний стан керуючого пристрою ( EMBED Equation.DSMT4 – початковий сан), EMBED Equation.DSMT4 – невикористана частина вхідного ланцюжка (якщо EMBED Equation.DSMT4 , то вхідний ланцюжок прочитаний), EMBED Equation.DSMT4 – вмістиме магазину (лівий символ є верхнім символом магазину, якщо EMBED Equation.DSMT4 , то магазин порожній). Початкова конфігурація МП–автомата – EMBED Equation.DSMT4 , кінцева, заключна – EMBED Equation.DSMT4 .
Означення. Мовою, визначальною або допустимою МП–автоматом, називається множина ланцюжків, які допускаються МП–автоматом.
Ланцюжок EMBED Equation.DSMT4 допускається МП–автоматом, якщо EMBED Equation.DSMT4 .
Функція переходів і виходів EMBED Equation.DSMT4 характеризує дії магазинного автомату при різних станах його керуючої частини, магазину і вхідних символах. Ці, в принципі не однозначні, дії можна звезти до одночасного виконання скінченого числа елементарних дій п’яти типів:
читання символу із вхідного каналу і перехід у наступний стан, який є функцією прочитаного символу і поточного стану автомату;
передача символу у вихідний канал і перехід у наступний стан. Вихідний символ і новий стан є функціями лише поточного стану автомата;
читання верхнього символу з магазину і перехід у наступний стан, який є функцією прочитаного символу і поточного стану автомату;
запис у магазин символу і перехід у новий стан. Символ, що записується, і новий стан автомата визначається його поточним станом;
перехід у новий стан, який є функцією поточного стану (так званий спонтанний перехід).
При такому означенні функції переходів і виходів функціонування магазинного автомату можна задати прямокутною таблицею. Стовпчики цієї таблиці відповідають станам автомату, а рядки розбиті на три секції:
секція читання вхідних символів, складається з рядків, які відповідають символам вхідного алфавіту;
секція читання символів із магазину складається із рядків, які відповідають символам магазинного алфавіту EMBED Equation.DSMT4 ;
секція запису, складається з рядка, в якому вказані ті символи вхідного або магазинного алфавіту, які передаються на запис у вихідний канал або канал магазину. Секція також включає стани, в які автомат може перейти спонтанно.
Приклад 1. Магазинний автомат, функція переходів і виходів якого задані в таблиці 1, працює таким чином. В стані 1 цей автомат або сприймає вхідний символ, або записує символ EMBED Equation.DSMT4 в магазин. Якщо на його вхід надійде символ EMBED Equation.DSMT4 , то автомат може залишатися в тому ж стані, або перейти в стан 4. В стані 2 автомат або читає символ із магазину, або видає символ EMBED Equation.DSMT4 у вихідний канал.
Таблиця переходів і виходів магазинного автомата
Таблиця 1
При читанні із магазину його верхній символ витирається (для цього символи EMBED Equation.DSMT4 і EMBED Equation.DSMT4 записані у від’ємному степені в другій секції таблиці). В стані 4 автомат або виконує спонтанний перехід в один із станів: 1 чи 2, або сприймає вхідний символ. При цьому якщо на його вхід подається символ EMBED Equation.DSMT4 , то перехід автомата вважається незавершеним, а стан невизначеним. Те саме буде і у випадку, коли автомат читає із магазину пустий символ.
Приклад 2. Побудувати МП–автомат, який визначає мову EMBED Equation.DSMT4 .
Нехай EMBED Equation.DSMT4 , де
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
Робота МП–автомата полягає в тому, що він копіює в магазин початкову частину вхідного ланцюжка, який складається з нулів, а потім видаляє з магазину по одному нулю на кожну одиницю на вході. Крім того, переходи станів гарантують, що всі нулі передують одиницям. Наприклад, для вхідного ланцюжка 0011 МП–автомат проробить таку послідовність тактів:
EMBED Equation.DSMT4 –> EMBED Equation.DSMT4
–> EMBED Equation.DSMT4
–> EMBED Equation.DSMT4
–> EMBED Equation.DSMT4
–> EMBED Equation.DSMT4
Представлення мов в магазинних автоматах
Назвемо перехід магазинного автомата зі стану EMBED Equation.DSMT4 в стан EMBED Equation.DSMT4 правильним, якщо як у початковому, так і в заключному стані цього переходу магазин автомата порожній. Іншими словами, перехід правильний, якщо всі символи, записані в процесі цього переходу в магазин, виявляються прочитаними з магазину, і автомат ніколи не намагається прочитати символи з магазину, які він туди не записував. Магазинний автомат називається налаштованим, якщо в ньому виділені початковий стан EMBED Equation.DSMT4 EMBED Equation.DSMT4 і множина заключних станів EMBED Equation.DSMT4 . Будемо говорити, що магазинний автомат сприймає вхідне слово EMBED Equation.DSMT4 ,якщо можливий такий правильний перехід із початкового стану в один із заключних станів, при якому прочитані по вхідному каналу символи складають слово EMBED Equation.DSMT4 . Магазинний автомат породжує слово EMBED Equation.DSMT4 , якщо можливий такий правильний перехід із початкового стану в один із заключних станів, при якому символи, подані на вихідний канал, складають слово EMBED Equation.DSMT4 . Будемо також говорити, що магазинний автомат сприймає (породжує) деяку мову EMBED Equation.DSMT4 , якщо він сприймає (породжує) всі слова цієї мови і тільки їх.
Теорема. Якщо мова EMBED Equation.DSMT4 породжується деяким магазинним автоматом EMBED Equation.DSMT4 , то існує магазинний автомат EMBED Equation.DSMT4 , що сприймає цю мову.
Доведення. Переходи з першої секції, які відповідають читанню символів вхідного алфавіту, перенесемо в третю і будемо їх інтерпретувати як переходи, що супроводжуються передачею символів у вихідний канал. І навпаки, переходи з третьої секції, які супроводжуються передачею символів у вихідний канал, перенесемо в першу секцію. При цьому, очевидно, правильний перехід із початкового стану EMBED Equation.DSMT4 в заключний стан EMBED Equation.DSMT4 , при якому сприймається слово EMBED Equation.DSMT4 і породжується слово EMBED Equation.DSMT4 , також буде правильним, але при цьому буде сприйматися слово EMBED Equation.DSMT4 , а породжуватись – слово EMBED Equation.DSMT4 .
Теорему доведено.
Це твердження дає можливість надалі обмежуватись магазинними автоматами без виходів, які можуть тільки сприймати мови.
Аналіз магазинних автоматів
Алгоритм аналізу магазинних автоматів будує таблицю переходів магазинного автомата за системою рівнянь, найменшим розв’язком якої є мова, що сприймається цим автоматом.
Позначимо через EMBED Equation.DSMT4 мову, що сприймається деяким магазинним автоматом, якщо стан EMBED Equation.DSMT4 – початковий, а стан EMBED Equation.DSMT4 – як єдиний заключний стан. Для позначення множини станів, в які можна перейти за один такт роботи із стану EMBED Equation.DSMT4 внаслідок елементарних переходів кожного з чотирьох типів, введемо такі позначення:
EMBED Equation.DSMT4 – для спонтанних переходів
EMBED Equation.DSMT4 – для переходів, при яких читається вхідний символ EMBED Equation.DSMT4
EMBED Equation.DSMT4 – для переходів, при яких читається символ EMBED Equation.DSMT4 із магазину
EMBED Equation.DSMT4 – для переходів, при яких виконується запис символу EMBED Equation.DSMT4 в магазин.
Позначимо EMBED Equation.DSMT4 множину всіх станів, в яких можливе читання символу EMBED Equation.DSMT4 із магазину, EMBED Equation.DSMT4 – події, які складаються із одного порожнього символу, якщо EMBED Equation.DSMT4 , і порожні, якщо EMBED Equation.DSMT4 . Згідно з означеннями правильних переходів і елементарних дій, які відповідають одному такту роботи даного автомата, мова EMBED Equation.DSMT4 визначається рівнянням
EMBED Equation.DSMT4 EMBED Equation.DSMT4
Розглядаючи систему таких рівнянь для всіх пар EMBED Equation.DSMT4 , можна одержати її найменший розв’язок, який і буде визначати сукупність мов EMBED Equation.DSMT4 . Якщо розглядати автомат EMBED Equation.DSMT4 як налаштований з початковим станом 1 і множиною заключних станів EMBED Equation.DSMT4 , то мова, що сприймається цим автоматом, буде виражатися співвідношенням
EMBED Equation.DSMT4
Приклад. Нехай EMBED Equation.DSMT4 – магазинний автомат без виходів, в якому 1 – початковий стан, 3 – заключний стан, а функція переходів задається в таблиці 1.
Таблиця 2
З таблиці переходів цього автомата легко визначити, що
EMBED Equation.DSMT4
EMBED Equation.DSMT4 , EMBED Equation.DSMT4 , EMBED Equation.DSMT4 ,
EMBED Equation.DSMT4 , EMBED Equation.DSMT4 .
Шукана система рівнянь, яка визначає мову, представлену в цьому автоматі, має такий вигляд:
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 ; EMBED Equation.DSMT4 .
Користуючись загальною рекурсивною схемою розв’язання таких систем рівнянь, приходимо в результаті до мови EMBED Equation.DSMT4 , яка нас цікавить:
EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 .
З другого рівняння випливає, що EMBED Equation.DSMT4 ; тоді EMBED Equation.DSMT4 .
Синтез магазинних автоматів
Алгоритм синтезу, який за КВ–граматикою EMBED Equation.DSMT4 будує магазинний автомат EMBED Equation.DSMT4 з початковим станом EMBED Equation.DSMT4 і єдиним заключним станом EMBED Equation.DSMT4 . Автомат EMBED Equation.DSMT4 сприймає мову EMBED Equation.DSMT4 , що породжується граматикою EMBED Equation.DSMT4 .
Вхідний алфавіт EMBED Equation.DSMT4 автомата EMBED Equation.DSMT4 збігається з термінальним алфавітом EMBED Equation.DSMT4 граматики EMBED Equation.DSMT4 . Магазинний алфавіт EMBED Equation.DSMT4 складається із символів нетермінального алфавіту і символів, які є двійниками термінальних: EMBED Equation.DSMT4 . Двійники введені для того, щоб виконувалась умова EMBED Equation.DSMT4 . Множину EMBED Equation.DSMT4 станів автомата опишемо в процесі задання функції переходів EMBED Equation.DSMT4 .
В початковому стані EMBED Equation.DSMT4 автомат записує символ EMBED Equation.DSMT4 в магазин і переходить в стан EMBED Equation.DSMT4 – єдиний заключний стан, знаходячись в якому автомат може читати символи з магазину.
Коли автомат EMBED Equation.DSMT4 читає з магазину символ EMBED Equation.DSMT4 (двійник термінального символу), то при цьому він переходить в стан, який позначається EMBED Equation.DSMT4 . Якщо після цього на вхід автомата EMBED Equation.DSMT4 подається символ EMBED Equation.DSMT4 , то він переходить в стан EMBED Equation.DSMT4 , а в решті випадків перехід із стану EMBED Equation.DSMT4 невизначений. Зазначимо, що множина EMBED Equation.DSMT4 – це всі стани автомата, в яких він може читати символи з вхідного каналу.
Якщо в стані EMBED Equation.DSMT4 автомат читає з магазину символ EMBED Equation.DSMT4 , то він переходить в стан EMBED Equation.DSMT4 . Із цього стану автомат може спонтанно перейти в один із станів EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 – всі ті і тільки ті слова в алфавіті EMBED Equation.DSMT4 , для яких у граматиці EMBED Equation.DSMT4 є продукції EMBED Equation.DSMT4 . Якщо EMBED Equation.DSMT4 містить продукцію EMBED Equation.DSMT4 , то за стан EMBED Equation.DSMT4 вибирається стан EMBED Equation.DSMT4 . Із стану EMBED Equation.DSMT4 автомат за кілька тактів роботи (число цих тактів дорівнює довжині слова EMBED Equation.DSMT4 ) переходить у стан EMBED Equation.DSMT4 . При цьому він записує в магазин слово EMBED Equation.DSMT4 і перша буква цього слова буде в магазині верхньою. При переході зі стану EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 , в стан EMBED Equation.DSMT4 як проміжні використовуються стани EMBED Equation.DSMT4 і т. д. В стані EMBED Equation.DSMT4 автомат EMBED Equation.DSMT4 записує в магазин символ EMBED Equation.DSMT4 , якщо EMBED Equation.DSMT4 або його двійник, якщо EMBED Equation.DSMT4 , і переходить в стан EMBED Equation.DSMT4 , якщо EMBED Equation.DSMT4 або EMBED Equation.DSMT4 , якщо EMBED Equation.DSMT4 . Таким чином, стани автомата EMBED Equation.DSMT4 , що забезпечують запис правих частин продукцій в магазин, можуть бути подані у вигляді EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 – початкове підслово правої частини деякої продукції граматики EMBED Equation.DSMT4 . Початкові підслова різних продукцій можуть збігатися.
Нетермінальні символи читаються з магазину в послідовності, яка відповідає лівому виведенню слова EMBED Equation.DSMT4 в граматиці EMBED Equation.DSMT4 (виведення EMBED Equation.DSMT4 і EMBED Equation.DSMT4 одержуються з EMBED Equation.DSMT4 застосуванням продукції до одного з нетермінальних символів, який називають лівим, якщо на кожному з EMBED Equation.DSMT4 кроків виведення продукція застосовується до найлівішого нетермінального символу).
Приклад. Синтезувати автомат, що сприймає мову EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 .
Згідно з наведеним вище алгоритмом синтезу визначимо вхідний і магазинний алфавіти, а також множину станів автомата EMBED Equation.DSMT4 , що синтезується: EMBED Equation.DSMT4 ,
EMBED Equation.DSMT4
Тепер можна побудувати таблицю переходів автомата, яка складається з семи рядків і тринадцяти стовпчиків.(Таблиця 3).
Слід зазначити, що описаний алгоритм не найкращий, оскільки побудовані за ним автомати не завжди прості. Так, у випадку праволінійних чи ліволінійних граматик мови, що породжуються цими граматиками, будуть регулярними, отже, можуть сприйматися скінченними автоматами. Описаний же алгоритм синтезу будує магазинний автомат, в якому магазин використовуться завжди. В цьому і полягає один з основних недоліків наведеного алгоритму синтезу.
Правила, за якими синтезується МП–автомат:
1. По правилах виводу КВ–граматики будуємо систему рівнянь, користуючись правилами побудови регулярних виразів:
EMBED Equation.DSMT4 EMBED Equation.DSMT4
EMBED Equation.DSMT4 EMBED Equation.DSMT4
EMBED Equation.DSMT4 EMBED Equation.DSMT4
1). Проіндексуємо вссі нетермінальні символи, які входять в праву частину.
2). Проіндексовані нетермінальні символи утворюють внутрішній алфавіт МП –автомата.
3). Якщо права частина рівнянь містить більше одного дизюнктивного члена, переносимо його в круглі дужки.
4). Розділяємо всі символи вертикальними рисками, які будуть задавати внутрішні стани автомата.
5). Стан, який передує відкритій дужці, автоматично поширює свою дію на початки всіх дизюнктивних членів.
6). Стан, який стоїть після закритої дужки, поширює свою дію на кінці всіх дизюнктивних членів. А всі решта станів нумерують зліва направо.
1, 5, 9 – початкові
2, 10, 6 – кінцеві.
2. Перевіряємо граматику і, якщо потрібно, позбуваємося лівої рекурсії за правилом:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
Отримаємо граматику:
EMBED Equation.DSMT4 EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
Перепозначимо EMBED Equation.DSMT4 .\
EMBED Equation.DSMT4 EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
Стан, якому відповідає стан після відкриваючої дужки, відповідає стану перед відкриваючою дужкою;
Всі стани після + нумеруються так, як стани після відкриваючої дужки;
Стан, який стоїть після закриваючої дужки, переноситься на номер стану перед +;
Стани, які залишилися, нумеруємо попорядку.
Формування таблиці.
І секція: зчитуваня символів з вхідної стрічки, містить термінальні символи алфавіту.
ІІ секція: запис нетермінальних символів і номерів початкових станів, які їм відповідають.
ІІІ секція: виштовхування зі стеку. Проти кожного нетермінального символу записуємо номер стану, який стоїть після нього. Заповнюються стовпці кінцевих станів.
Еквівалентність МП–автоматів та КВ–мов
Типи граматик (ієрархія Хомського)
Продукція граматики дає змогу замінювати одну послідовність символів іншою. Граматики класифікують за типами продукцій. Найчастіше використовують класифікацію, яку запропонував Н. Хомський.
Граматика типу 2 має продукції лише у формі EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 – нетермінальний символ. Цю граматику називають контекстно вільною, оскільки нетермінал EMBED Equation.DSMT4 може бути замінений ланцюжком EMBED Equation.DSMT4 у довільному оточенні щоразу, коли він зустрічається, тобто незалежно від контексту.
Граматику типу 1 називають контекстно залежною. Коли у такій граматиці є продукція EMBED Equation.DSMT4 (тобто EMBED Equation.DSMT4 , EMBED Equation.DSMT4 ), у якій хоча б один з ланцюжків EMBED Equation.DSMT4 , EMBED Equation.DSMT4 відмінний від EMBED Equation.DSMT4 , то термінал EMBED Equation.DSMT4 може бути замінений ланцюжком EMBED Equation.DSMT4 лише в оточенні EMBED Equation.DSMT4 та EMBED Equation.DSMT4 , тобто у відповідному контексті, звідси походить назва.
Граматику типу 3 називають регулярною. Ця граматика може мати лише продукції у формі EMBED Equation.DSMT4 , EMBED Equation.DSMT4 , EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 , EMBED Equation.DSMT4 – нетермінали, EMBED Equation.DSMT4 – термінал.
Відповідно до граматик відбувається й класифікація мов. Мову називають контекстно залежною, якщо існує контекстно залежна граматика, яка породжує цю мову. Мову називають контекстно вільною, якщо існує контекстно вільна граматика, яка породжує цю мову. Аналогічно для двох інших типів мов.
Поняття недетермінованості скінченного розпізнавача набуває практичного значення завдяки наступному факту – для кожного недетермінованого скінченного розпізнавача існує детермінований скінчений розпізнавач, який допускає в точності ті ж вхідні ланцюжки, що і недетермінований.
Процедура задається п'ятьма кроками. Нехай EMBED Equation.DSMT4 – недетермінований автомат, а EMBED Equation.DSMT4 – еквівалентний йому детермінований, которий потрібно побудувати.
1 крок. Замінити перший рядок таблиці переходів для EMBED Equation.DSMT4 множиною початкових станів автомата EMBED Equation.DSMT4 .
2 крок. За даною множиною станів EMBED Equation.DSMT4 , що позначає рядок таблиці переходів автомата EMBED Equation.DSMT4 , для якої переходи ще не вираховані, обчислити ті стани EMBED Equation.DSMT4 , які можуть бути досягнуті EMBED Equation.DSMT4 за допомогою кожного вхідного символу EMBED Equation.DSMT4 , і помістити множини подальших станів у відповідні елементи таблиці для EMBED Equation.DSMT4 .
Символічно це виражається так: якщо EMBED Equation.DSMT4 – функція недетермінованих переходів, то функція детермінованих переходів EMBED Equation.DSMT4 задається формулою EMBED Equation.DSMT4 .
3 крок. Для кожної нової множини, породженї переходами на кроці 2, подивитись, чи є вже в EMBED Equation.DSMT4 рядок, помічений станом. Якщо немає, то створити новий рядок і помітити його станом. Якщо множина вже використовувалася як цільова, нияких дій не вимагається.
4 крок. Якщо в таблиці автомата EMBED Equation.DSMT4 є рядок, для якого ще не обчислені переходи, повернутися назад і застосувати до цього рядка крок 2, інакше перейти до кроку 5.
5 крок. Відмітити рядок як додатковий стан автомата EMBED Equation.DSMT4 тоді, коли він містить допустимий стан недетермінованного автомата. Інакше відмітити як виштовхуючий стан.
Приклад. Побудувати МП–автомат, для якого EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 – граматика, що визначає арифметичні вирази.
Нехай EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 визначається так:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4 .
При вході EMBED Equation.DSMT4 для EMBED Equation.DSMT4 можлива інша послідовність тактів:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4 .
Відмітимо, що обчислення МП–автомата відповідає лівому виводу ланцюжка EMBED Equation.DSMT4 з EMBED Equation.DSMT4 в КВ–граматиці EMBED Equation.DSMT4 .
Тип синтаксичного аналізу, що проводиться МП–автоматом, називається низхідним аналізом.
Можна побудувати розширений МП–автомат, який працює від низу до верху як висхідний аналізатор.
Варіанти МП–автоматів
Як і у випадку скінченних автоматів існує дві моделі магазинних автоматів – недетерміновані і детерміновані.
Розширений МП–автомат
Розширений МП–автомат за один такт дозволяє замінити не один верхній символ магазину, а ланцюжок символів обмеженої довжини, розташований в верхній частині магазину, іншим ланцюжком скінченої довжини.
Розширений автомат визначається так само
EMBED Equation.DSMT4 EMBED Equation.DSMT4 ,
але відрізняється однією функцією управління EMBED Equation.DSMT4 – відображення скінченої підмножини множини EMBED Equation.DSMT4 в множину скінчених підмножин множини EMBED Equation.DSMT4
Приклад. Визначимо розширений МП–автомат, який розпізнає мову EMBED Equation.DSMT4 . Нехай EMBED Equation.DSMT4 , де
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
Недетерміновані МП–автомати
В недетермінованій моделі автомат кожен раз має можливість певного скінченого вибору рухів і виконує один із них. Вхідний ланцюжок вважається сприйнятим, якщо існує хоча б одна послідовність вибору рухів, яка приводить автомат до кінцевої конфігурації – вхідний ланцюжок прочитаний, поточний стан – кінцевий або (в другому варіанті) магазин пустий. В іншому випадку вона не приймається. Множина всіх ланцюжків, які сприймає даний МП–автомат, називається мовою, яка розпізнається цим МП–автоматом.
Автомат з магазинною пам’яттю – це недетермінований розпізнавач, в потенціально безкінечній пам’яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожний момент доступний тільки верхній елемент магазину. Операції над магазином: помістити в магазин певний символ, виштовхнути верхній символ, залишити магазин без змін.
На кожному кроці автомата конфігурація його пам’яті може змінюватися за рахунок переходу в новий стан, а також запису символу в магазин або зчитування з нього. На відміну від скінченого автомата МП–автомат може опрацьовувати один вхідний символ на протязі декількох кроків.
Детерміновані МП–автомати
МП–автомати володіють одним суттєвим недоліком – вони недетерміновані за своєю природою. На практиці хотілось би мати справу з детермінованими автоматами, в яких в кожній конфігурації допустимий тільки один такт.
Детерміновані МП–автомати описують тільки підмножину класу КВ–мов – цю підмножину називають детермінованими КВ–мовами. Цей клас називають також LR(k)–граматиками, оскільки вони можуть бути однозначно розібрані шляхом перегляду ланцюжка зліва на право з перегляданням на перед не більше, ніж k символів.
Детерміновані КВ–мови, як і весь клас КВ–мов, дозволяють перевірити, чи порожній ланцюжок мови, який визначається. Але детерміновані КВ–мови не володіють деякими важливими теоретико–множинними властивостями. Тим не менше, з точки зору методів компіляції, клас LR(k)–граматик надзвичайно важливий.
Детерміновані МП–автомати
МП–автомат EMBED Equation.DSMT4 називається детермінованим (ДМП), якщо для всіх EMBED Equation.DSMT4 EMBED Equation.DSMT4 виконується одна з наступних умов:
EMBED Equation.DSMT4 містить не більше одного елемента для кожного EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4 і EMBED Equation.DSMT4 містить не більше одного елемента.
В силу цих двох обмежень ДМП–автомат в будь–якій конфігурації може вибрати не більше одного такту.
Розглянемо ДМП–автомат, який розпізнає мову EMBED Equation.DSMT4 . Нехай EMBED Equation.DSMT4 , де EMBED Equation.DSMT4 це:
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4 і EMBED Equation.DSMT4
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4
EMBED Equation.DSMT4 .
До тих пір, поки EMBED Equation.DSMT4 не побачить маркер EMBED Equation.DSMT4 , який відмічає середину, він записує в магазині символи вхідного ланцюжка. Коли EMBED Equation.DSMT4 досягає EMBED Equation.DSMT4 , він переходить в стан EMBED Equation.DSMT4 і далі порівнює частину вхідного ланцюжка, яка ще залишилась, з вмістимим магазину.
Розширений МП–автомат називається детермінованим, якщо виконуються наступні умови:
EMBED Equation.DSMT4 для всіх EMBED Equation.DSMT4 ;
якщо EMBED Equation.DSMT4 , EMBED Equation.DSMT4 і EMBED Equation.DSMT4 , то жоден з ланцюжків EMBED Equation.DSMT4 і EMBED Equation.DSMT4 не являються суфіксом (префіксом) іншого;
якщо EMBED Equation.DSMT4 і EMBED Equation.DSMT4 , то жоден з ланцюжків EMBED Equation.DSMT4 і EMBED Equation.DSMT4 не являються суфіксом (префіксом) іншого.
Конфігурація EMBED Equation.DSMT4 ДМП–автомата EMBED Equation.DSMT4 називається зациклюючою, якщо для кожного EMBED Equation.DSMT4 знайдеться така конфігурація EMBED Equation.DSMT4 , що EMBED Equation.DSMT4 і EMBED Equation.DSMT4 .
Таким чином конфігурація зациклююча, якщо EMBED Equation.DSMT4 може робити безкінечне число EMBED Equation.DSMT4 –тактів, не скорочуючи магазин (може рости).
Алгоритм виявлення зациклюючої конфігурації:
Вхід: ДМП–автомат EMBED Equation.DSMT4 .
Вихід:
EMBED Equation.DSMT4 – зациклююча конфігурація і не існує такого EMBED Equation.DSMT4 ( EMBED Equation.DSMT4 , що EMBED Equation.DSMT4 для ланцюжка EMBED Equation.DSMT4 ) EMBED Equation.DSMT4 ;
EMBED Equation.DSMT4 – зациклююча конфігурація, EMBED Equation.DSMT4 для деяких EMBED Equation.DSMT4 EMBED Equation.DSMT4 .
Висновок
Скінченний автомат може вирішувати лише такі задачі, які вимагають фіксованого і кінцевого об’єму пам'яті. Проте у компіляторі виникає багато завдань, які не можуть бути вирішені при такому обмеженні і тому потрібна модель складнішого автомата.
Такий автомат розглянуто в даній курсовій роботі. Це автомат з магазинною пам'яттю – недетермінований розпізнавач, в потенційно нескінченній пам'яті якого елементи інформації зберігаються і використовуються так само, як патрони в магазині автоматичної зброї, тобто в кожен момент доступний тільки верхній елемент магазину. Операції над магазином: заштовхнути в магазин певний символ, виштовхнути верхній символ, залишити магазин без зміни.
У MП-автоматі комбінується пам'ять кінцевого автомату і магазинна пам'ять. MП-автомат може знаходиться в одному з скінченного числа станів і має магазин, куди він може поміщати і звідки може витягувати інформацію.
На кожному кроці дії автомата конфігурація його пам'яті може змінюватися за рахунок переходу в новий стан, а також заштовхування символу в магазин або виштовхування з нього. На відміну від скінченного автомата MП-автомат може обробляти один вхідний символ протягом декількох кроків.
Використовується інформація: стан, верхній символ магазина поточний вхідний символ. Множина правил процесу обробки називається пристроєм, що управляє пристроєм.
В даній роботі подана теорія, розглянуто принцип роботи МП-автомата, те як представляються мови в даних автоматах. Було проаналізовано МП-автомат, показано, як його синтезувати. В даному виді автоматів застосовуються КВ-граматики, тому порушується питання ієрархії Хомського і еквівалентності МП-автоматів та КВ-граматик. Також розглянуто варіанти МП-автоматів і детальніше вивчалися детерміновані МП-автомати.
Практичне застосування МП-автоматів – це написана програма, яка перевіряє на правильність введений арифметичний вираз.
Додатки Література
Зміст
Вступ._____________________________________________________1
Базові означення МП–автоматів._______________________________4
Означення МП–автомата. Принцип роботи. Приклади._________4
Представлення мов в магазинних автоматах.__________________9
Аналіз магазинних автоматів.___________________________________10
Синтез магазинних автоматів .___________________________________13
Еквівалентність МП–автоматів та КВ–мов.________________________19
Типи граматик (ієрархія Хомського).________________________19
Варіанти МП–автоматів.________________________________________22
Розширений МП–автомат.__________________________________22
Недетерміновані МП–автомати._____________________________22
Детерміновані МП–автомати.____________________________________22
Детерміновані МП–автомати._______________________________24
Алгоритм виявлення зациклюючої конфігурації._______________25
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора