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