ЛК.12 - Аналіз стану

Використання кінцевого автомату: синтаксичний аналіз.
Реалізація синтаксичного аналізу файлу з

розділяючими комами.
Детерміновані та недетерміновані кінцеві автомати.

Перелік питань

стану об’єкту в залежності від його поточного стану та вхідних

даних, за умови, що кількість станів є кінцевою.
Приклад задання кінцевого автомату:
M = (Q, Σ, δ, q0, F),
де Q – кінцева множина станів автомату;
q0- початковий стан автомату;
F – множина заключних чи допускаючих станів, таких, що F входить в Q;
Σ – допустимий вхідний алфавіт (кінцева множина допустимих символів), із якого формуються рядки, що зчитуються автоматом;
δ – функція переходів автомату: δ : Q × Σ  P (Q)

1. Введення до теорії кінцевих автоматів

стани автомата (на рисунку їх 5).
Допускаючий стан (другий) помічений

подвійною межею кола. Стрілки (ребра графа) зображають таблицю правил переходу. Стрілка, для якої не задано стан, звідки вона спрямована, відображає початковий стан.

2. Графічне представлення кінцевих автоматів

Використання кінцевого автомату: синтаксичний аналіз.

комами (CSV) – типова задача, яка для свого вирішення вимагає

використання кінцевих автоматів.

Допустимо, ми маємо файл, рядки якого наведені у наступному вигляді:
Julian, Bucknall,,43, “Author, and Columnist”

Наведений рядок містить п’ять полів:
Julian
Bucknall
<Без значення>
43
Author, and Columnist

4. Реалізація синтаксичного аналізу файлу з розділяючими комами

з розділяючими комами

одного стану лише у один наступний стан.
В той час, недетерміновайни

кінцевий автомат, як і НМТ може переходити у декілька станів, створюючи стільки копій автомату, до скількох додаткових станів необхідно перейти.
Приклад недетермінованого кінцевого автомату:

5. Детерміновані та недетерміновані кінцеві автомати