Узагальнений недетермінований скінченний автомат

Узагальнений недетермінований скінченний автомат, скорочено УНСА, — це недетермінований автомат, на переходах якого можуть бути не лише символи алфавіту, а й регулярні вирази.

Означення

УНСА знадобиться нам в алгоритмі перетворення скінченного автомата на регулярний вираз. УНСА — це НСА, переходи якого задано регулярними виразами. Приклад такого УНСА:

Бачимо, що, наприклад, зі стану q₂ веде перехід у стан q_f, позначений регулярним виразом $a^\ast b$. Інші вимоги до УНСА:

• Початковий стан q₀ повинен мати перехід у всі інші стани. На рисунку видно, що зі стану q₀ ведуть переходи в усі інші стани.
• В УНСА є лише один заключний стан, і всі інші стани мають перехід у цей стан. Як видно на рисунку, з усіх станів іде стрілка в q_f.
• Початковий стан не може збігатися із заключним. Отже, УНСА має щонайменше два стани.
• Усі інші стани, окрім початкового й заключного, повинні мати переходи в усі інші стани, окрім початкового й заключного. Зокрема й петлі (перехід зі стану q_i у стан q_i).

Перетворення звичайного НСА на УНСА

Якщо маємо якийсь НСА, перетворити його на УНСА просто.

1. Створюємо новий початковий стан q_s і ε-перехід у початковий стан вихідного автомата.
2. Створюємо новий заключний стан q_f і з усіх колишніх заключних станів проводимо ε-переходи в стан q_f. Колишні заключні стани стають звичайними станами.
3. Якщо десь є кратний перехід (тобто якщо зі стану q₁ можна потрапити в стан q₂ і за символом 0, і за символом 1), то ці переходи об'єднуємо в один регулярний вираз, а всі ці символи з'єднуємо оператором об'єднання (тобто стрілку позначаємо регулярним виразом 0|1).
4. Якщо в автоматі бракує якогось переходу, який за означенням мав би бути, створюємо його й позначаємо регулярним виразом ∅. Мова, яку допускає автомат, від цього не змінюється, бо такий перехід ніколи не виконається.

Цей автомат можна використати для перетворення автомата на регулярний вираз.