Головна

Магазинні автомати

  1. III. Движение поездов при неисправности полуавтоматической блокировки
  2. quot;B1", "C1", "D1" С АВТОМАТИЧЕСКОЙ ТРАНСМИССИЕЙ
  3. RFID (Radio Frequency IDentification) - автоматическая идентификация продукта при помощи радиочастотных меток.
  4. VI. Движение поездов при автоматической локомотивной сигнализации, применяемой как самостоятельное средство сигнализации и связи
  5. А) Системы автоматизации отдельных разделов бухгалтерского учета.
  6. АВС-36, автоматическая винтовка Симонова образца 1936 г.
  7. Автоматизация анализа финансового состояния предприятия

Означення. Магазинний автомат - це сімка ,

де: - множина станів магазинного автомату;

- основний алфавіт;

- допоміжний алфавіт (алфавіт магазина);

- початковий стан магазинного автомату;

- початковий вміст магазину;

;

- множина заключних станів автомата .

Поточний стан магазинного автомата описується конфігурацією. Конфігурація магазинного автомата - це трійка , де . Серед конфігурацій магазинного автомата виділимо дві:

- початкова конфігурація , де , - вхідне слово ( ),

;

- заключна конфігурація , . В загальній теорії магазинних автоматів іноді як заключну конфігурацію розглядають , де - фіксована пара. Легко довести, що визначення заключної конфігурації виду не зменшує потужності класу магазинних автоматів.

Такт роботи (позначається ╞═ ) магазинного автомата - це перехід від однієї конфігурації до іншої, а точніше:

╞═ при умові, що .

Робота магазинного автомата (позначається ╞═*) - це послідовність тактів роботи, а точніше: ╞═* тоді і тільки тоді, коли ╞═ , ╞═ ,..., ╞═ .

Операції ╞═ та ╞═* можна трактувати як бінарні відношення на відповідних кортежах. Тоді робота магазинного автомата - це рефлексивно-транзитивне замикання бінарного відношення ╞═.

Означення. Мова, яку розпізнає магазинний автомат (позначається ) - це множина ланцюжків, які задовольняють умові:

╞═* .

Зафіксуємо наступні результати теорії магазинних автоматів:

- Не існує алгоритму перетворення недетермінованого магазинного автомата у еквівалентний йому детермінований магазинний автомат.

- Існує алгоритм, який вирішує проблему порожньої множини для конкретного магазинного автомата.

- Існує алгоритм, який за час, пропорційний перевіряє, чи належить мові, яку розпізнає магазинний автомат .

- Клас мов, які розпізнаються магазинними автоматами, співпадає з класом мов, що породжуються КС-граматиками.

На основі сформульованих вище результатів для лівосторонньої стратегії виводу в запропонуємо наступне твердження: для довільної КС-граматики можна побудувати магазинний автомат такий, що . При цьому автомат буде моделювати лівосторонню стратегію виводу в .

Нехай - КС-граматика. Побудуємо відповідний МП-автомат :

- - множину станів автомата складає один стан ;

- - допоміжний алфавіт;

- - початковий вміст магазина.

§ функцію визначимо так:

якщо належить , то

.

також поповнимо множину значень функції наступними значеннями:

.

Для ланцюжка , покажемо, якщо ми за кроків безпосереднього виводу , то відповідний автомат за кроків допустить . Зробимо перший крок безпосереднього виведення тоді МП-автомат з початкової конфігурації перейде в наступну конфігурацію . Далі розглянемо наступні ситуації:

- коли - термінал (тобто ), тоді МП-автомат виконає наступний такт: ╞═ ;

- коли - нетермінал, тоді в схемі граматики виберемо правило виду , зробимо наступний крок безпосереднього виведення : . При таких умовах автомат перейде в наступну конфігурацію: ╞═ .

Очевидно, якщо ланцюжок виводиться за кроків, то МП-автомат зробить кроків та розпізнає . Таким чином, .

 



Мал. 2. | Синтаксичний аналіз без повернення назад

Скінчені автомати | Мінімізація детермінованих скінчених автоматів | Скінчені автомати та праволінійні граматики | Регулярні множини та регулярні вирази | Польський інверсний запис для регулярних виразів | Застосування скінчених автоматів при розробці лексичних аналізаторів | На основі поточного стану. | Методика програмування лексичних аналізаторів на основі скінчених автоматів. | Лабораторний практикум побудови лексичних аналізаторів. | Синтаксичний аналіз в мовних процесорах |

© um.co.ua - учбові матеріали та реферати