Восток Маркетинг


Статьи

НОУ ІНТУЇТ | лекція | Автомати з магазинною пам'яттю

  1. 10.1. Визначення автомата з магазинної пам'яттю

Анотація: У даній лекції розглядаються автомати з магазинною пам'яттю, в яких крім обмеженою пам'яті, що зберігає поточний стан, є потенційно нескінченна пам'ять, яка використовується як магазин. Даються необхідні визначення, і доводиться, що автомати з магазинною пам'яттю розпізнають в точності контекстно-вільні мови. Наведені приклади практичного використання автоматів з магазинної пам'яттю і наведені вправи для самостійного опрацювання

Подібно до того, як праволінейним граматика відповідають кінцеві автомати, контекстно-вільним граматика відповідають автомати з магазинною пам'яттю (МП-автомати). В такому автоматі, крім обмеженою пам'яті, що зберігає поточний стан, є потенційно нескінченна пам'ять, яка використовується як стек (магазин), тобто структура даних, де в кожен момент доступний тільки той елемент, який був доданий пізніше за інших присутніх на даний момент елементів.

Для наочності стек зазвичай зображують вертикально, так, що доступний елемент даних (вершина) знаходиться нагорі. Але при формальному визначенні конфігурації (миттєвого стану) МП-автомата зручно вважати весь вміст стека кінцевої послідовністю символів, тобто словом (в алфавіті, в якому перераховані всі можливі дані, "уміщаються" в одній комірці стека). Перш ніж визначити конфігурацію, доведеться прийняти довільне угоду про те, в якому порядку записувати вміст стека в цьому слові. У цій книзі вважається, що вершина стека знаходиться на початку слова (тобто зліва). У розділі 10.1 даються необхідні визначення. У розділі 10.2 доводиться, що МП-автомати розпізнають в точності контекстно-вільні мови.

10.1. Визначення автомата з магазинної пам'яттю

Визначення 10.1.1. Автомат з магазинної пам'яттю (МП-автомат, магазинний автомат, стековий автомат, pushdown automaton) - це шістка Визначення 10 , де , , і - кінцеві безлічі, , і

Тут Q - безліч станів, Тут Q - безліч станів,   - вхідний алфавіт,   - алфавіт магазинної пам'яті (stack alphabet),   - безліч переходів (transition relation), елементи I називаються початковими станами, елементи F - заключними або допускають станами - вхідний алфавіт, - алфавіт магазинної пам'яті (stack alphabet), - безліч переходів (transition relation), елементи I називаються початковими станами, елементи F - заключними або допускають станами.

Приклад 10.1.2. Нехай Q = {1,2}, Приклад 10 , ,

Нехай Q = {1,2},   ,   ,

, , . тоді - МП-автомат.

Зауваження 10.1.3. МП-автомати можна зображувати у вигляді діаграм станів. На діаграмі кожне стан позначається кружком, а перехід - стрілкою. Кожне початковий стан розпізнається по провідній в нього короткою стрілкою. Кожне допускає стан відзначається на діаграмі подвійним кружком. Стрілка з позначкою Зауваження 10 , Яка веде з p в q, показує, що є переходом даного МП-автомата.

Приклад 10.1.4. Нижче приведена діаграма МП-автомата з прикладу 10.1.2.

Визначення 10.1.5. Конфігурацією МП-автомата називається будь-яка трійка Визначення 10 , де , , .

Визначення 10.1.6. Визначимо на множині всіх конфігурацій МП-автомата Визначення 10 бінарне відношення (Такт роботи) наступним чином. якщо , і , то .

Зауваження 10.1.7 Зазвичай з контексту ясно, про яке МП-автоматі йде мова. тоді замість Зауваження 10 будемо писати .

Приклад 10.1.8. Для МП-автомата з прикладу 10.1.2 виконується Приклад 10 і .

Визначення 10.1.9. бінарне відношення Визначення 10 визначається як рефлексивне, транзитивне замикання відношення .

Приклад 10.1.10. Для МП-автомата з прикладу 10.1.2 виконується Приклад 10 і .

Лемма 10.1.11. якщо Лемма 10 і , то .

Доказ. Лему легко довести індукцією за кількістю тактів в обчислювальному процесі, що веде з конфігурації Доказ в конфігурацію .

Визначення 10.1.12. слово Визначення 10 допускається МП-автоматом , Якщо знайдуться такі стани і , що .

Визначення 10.1.13. Мова, розпізнається МП-автоматом, - безліч всіх слів, що допускаються цим МП-автоматом. Мова, розпізнається МП-автоматом M, позначається L (M).

Зауваження 10.1.14. Зазвичай в підручниках використовується більш вузьке визначення МП-автомата, але це не змінює класу мов, які розпізнаються МП-автоматами.

Приклад 10.1.15. нехай Приклад 10 - МП-автомат з прикладу 10.1.2. тоді .

Приклад 10.1.16. нехай Приклад 10 . Розглянемо МП-автомат , де , , I = {1}, F = {4,5} і

тоді тоді .

Визначення 10.1.17. Два МП-автомата еквівалентні, якщо вони розпізнають один і той же мова.

Зауваження 10.1.18. В даному посібнику не розглядаються перетворювачі з магазинної пам'яттю (pushdown transducer) узагальнення автоматів з магазинної пам'яттю за допомогою додавання "вихідного" потоку (див. [7, 3.5] або [2, 3.1.4] ).

Зауваження 10.1.19. Деякі автори змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом Зауваження 10 , Якщо знайдуться такі стани і і послідовність , що . Таке визначення не змінює класу мов, які розпізнаються МП-автоматами.

Зауваження 10.1.20. Деякі автори додають в визначення МП-автомата сьому компоненту - Z0, звану маркером магазинної пам'яті (start pushdown symbol), і змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом Зауваження 10 , Якщо знайдуться такі стани і , що . Таке визначення не змінює класу мов, які розпізнаються МП-автоматами.

Зауваження 10.1.21. Клас мов, які розпізнаються МП-автоматами, не зміниться також, якщо використовувати наступну природну комбінацію двох попередніх визначень: слово w допускається МП-автоматом Зауваження 10 , Якщо знайдуться такі стани і і послідовність , що .

Зауваження 10.1.22. Деякі автори додають в визначення МП-автомата маркер магазинної пам'яті Z0, відкидають безліч F і змінюють визначення допустимих слів наступним чином: слово w допускається МП-автоматом Зауваження 10 , Якщо знайдуться такі стани і , що . Це також не змінює класу мов, які розпізнаються МП-автоматами.

Вправа 10.1.23. Знайти МП-автомат, що розпізнає мову Вправа 10

Вправа 10.1.24. Знайти МП-автомат, що розпізнає мову Вправа 10

Вправа 10.1.25. Знайти МП-автомат, що розпізнає мову Вправа 10

Новости

также можем предложить:
печать бланков и прайс-листов | печать визитных карточек (визиток)
изготовление папок и меню | изготовление блокнотов
печать листовок

Связаться с менеджером для оформления заказа:
тел.: +38 (062) 349-56-15, 348-62-20
моб.: +38 (095) 811-22-62, +38 (093) 665-38-06,
+38 (067) 17 44 103
факс: +38 (062) 332-28-98
e-mail: [email protected]
г. Донецк, ул. Артема, 41

   2010 © Восток Маркетинг Яндекс.Метрика