![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Означення. Магазинний автомат — це сімка
,
де: — множина станів магазинного автомату;
— основний алфавіт;
— допоміжний алфавіт (алфавіт магазина);
— початковий стан магазинного автомату;
— початковий вміст магазину;
;
— множина заключних станів автомата
.
Поточний стан магазинного автомата описується конфігурацією. Конфігурація магазинного автомата
— це трійка
, де
. Серед конфігурацій магазинного автомата
виділимо дві:
- початкова конфігурація , де
,
— вхідне слово (
),
;
- заключна конфігурація ,
. В загальній теорії магазинних автоматів іноді як заключну конфігурацію розглядають
, де
- фіксована пара. Легко довести, що визначення заключної конфігурації виду
не зменшує потужності класу магазинних автоматів.
Такт роботи (позначається ╞═) магазинного автомата — це перехід від однієї конфігурації до іншої, а точніше:
╞═
при умові, що
.
Робота магазинного автомата (позначається ╞═*) — це послідовність тактів роботи, а точніше:
╞═*
тоді і тільки тоді, коли
╞═
,
╞═
,…,
╞═
.
Операції ╞═ та ╞═* можна трактувати як бінарні відношення на відповідних кортежах. Тоді робота магазинного автомата — це рефлексивно-транзитивне замикання бінарного відношення ╞═.
Означення. Мова, яку розпізнає магазинний автомат (позначається
) - це множина ланцюжків, які задовольняють умові:
╞═*
.
Зафіксуємо наступні результати теорії магазинних автоматів:
- Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат.
- Існує алгоритм, який вирішує проблему порожньої множини для конкретного магазинного автомата.
- Існує алгоритм, який за час, пропорційний перевіряє, чи належить
мові, яку розпізнає магазинний автомат
.
- Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками.
На основі сформульованих вище результатів для лівосторонньої стратегії виводу в
запропонуємо наступне твердження: для довільної КС-граматики
можна побудувати магазинний автомат
такий, що
. При цьому автомат буде моделювати лівосторонню стратегію виводу
в
.
Нехай — КС-граматика. Побудуємо відповідний МП-автомат
:
- — множину станів автомата складає один стан
;
- — допоміжний алфавіт;
- — початковий вміст магазина.
§ функцію визначимо так:
якщо належить
, то
.
також поповнимо множину значень функції наступними значеннями:
.
Для ланцюжка ,
покажемо, якщо ми за
кроків безпосереднього виводу
, то відповідний автомат за
кроків допустить
. Зробимо перший крок безпосереднього виведення
тоді МП-автомат з початкової конфігурації
перейде в наступну конфігурацію
. Далі розглянемо наступні ситуації:
- коли — термінал
(тобто
), тоді МП-автомат виконає наступний такт:
╞═
;
- коли — нетермінал, тоді в схемі
граматики
виберемо правило виду
, зробимо наступний крок безпосереднього виведення:
. При таких умовах автомат перейде в наступну конфігурацію:
╞═
.
Очевидно, якщо ланцюжок виводиться за
кроків, то МП-автомат зробить
кроків та розпізнає
. Таким чином,
.
Дата публикования: 2015-04-06; Прочитано: 590 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!