✖

Перетворення автомата на регулярний вираз

Kapitoly: Регулярні вирази, Регулярний вираз → автомат, Узагальнений НСА, Автомат → регулярний вираз

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

Опис алгоритму

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

Вилучення одного стану

Як вилучити один стан, покажемо на простому прикладі. Припустімо, що частина нашого автомата виглядає так:

де Ri — деякі регулярні вирази. Як виглядатиме автомат, якщо вилучити стан qr? Уявімо, що ми перебуваємо в стані qi і запитуємо себе, які слова можна породити на цій ділянці. Якщо йти зі стану qi просто в стан qj, це будуть усі слова, що відповідають регулярному виразу R4.

Якщо ж ми підемо в стан qr, то зможемо породити слова вигляду R1. Але в стані qr можна ходити по петлі за регулярним виразом R2, тож насправді можна породити слова вигляду $R_1\circ(R_2^\ast)$. А оскільки зі стану qr ще можна потрапити в стан qj, додаємо ще регулярний вираз R3. Загалом цим шляхом можна отримати слова вигляду $R_1\circ(R_2^\ast)\circ R_3$.

Тепер знаємо, що з цієї частини автомата можуть виникнути слова вигляду R4 або вигляду $R_1\circ(R_2^\ast)\circ R_3$. Це, звісно, можна записати як регулярний вираз $(R_4)|(R_1\circ(R_2^\ast)\circ R_3)$.

Тепер можна просто вилучити стан qr, залишити лише два стани qi і qj, а замість R4 записати щойно обчислений регулярний вираз:

Цю процедуру виконуємо для кожного переходу з кожного стану qi в якийсь стан qj, зокрема й для петель, тобто й для випадку qi = qj.

Після вилучення одного стану отримуємо еквівалентний автомат — автомат, що розпізнає ту саму мову.

Увесь алгоритм

На вході маємо НСА $A=\left<Q, \Sigma, \delta, q_0, F\right>$.

  1. Перетворюємо НСА A на УНСА $Z=\left<Q^\prime, \Sigma, \delta^\prime, q_0^\prime, q_f^\prime\right>$. Далі буквою k позначатимемо кількість станів у Z.
  2. Якщо k = 2, алгоритм завершується, а на переході між початковим і заключним станами стоїть шуканий регулярний вираз.
  3. Якщо k>2, вибираємо довільний стан qr, відмінний від початкового й заключного, тобто $q_r\ne q_0^\prime$ і $q_r\ne q_f^\prime$. Далі створюємо новий УНСА $Z^\prime=\left<Q^{\prime\prime}, \Sigma, \delta^{\prime\prime},q_0^{\prime},q_f^{\prime}\right>$, для якого виконуватиметься: $$ Q^{\prime\prime}=Q^\prime\setminus\left\{q_r\right\} $$ і для всіх $q_i\in Q^{\prime\prime}\setminus\left\{q_f^\prime\right\}$ та для всіх $q_j\in Q^{\prime\prime}\setminus \left\{q_0^\prime\right\}$ нехай $$ \delta^{\prime\prime}(q_i, q_j)=(R_4)|(R_1(R_2^\ast)R_3), $$ де $R_1=\delta^\prime(q_i,q_r)$, $R_2=\delta^\prime(q_r,q_r)$, $R_3=\delta^\prime(q_r, q_j)$, $R_4=\delta^\prime(q_i, q_j)$. Далі повертаємося до кроку 2.

Приклад

Нехай на вході маємо такий скінченний автомат:

Спочатку перетворюємо його на УНСА (зайвих ∅-переходів не зображуватимемо):

Тепер застосуємо другу частину алгоритму й вилучимо якийсь стан. Почнемо зі стану q2. Вилучаємо стан q2 і додаємо перехід зі стану q1 у стан qf. Цей перехід позначимо $b(a|b)^\ast$, бо зі стану q1 у стан q2 потрапляємо за словом b, потім можемо ходити по петлі за a|b, отримуючи $(a|b)^\ast$, і нарешті ε-переходом потрапляємо в qf. При цьому $b(a|b)^\ast\epsilon=b(a|b)^\ast$. Отримаємо автомат:

Залишилося вилучити останній стан, q1. Додаємо перехід зі стану qs у стан qf. Як його позначити? У стан q1 потрапляємо ε-переходом, його можна одразу опустити. Потім можемо ходити по петлі за a, тож отримуємо регулярний вираз $a^\ast$. І нарешті цим переходом потрапляємо в qf, тож вираз ще конкатенуємо з $b(a|b)^\ast$. Отже, перехід позначаємо регулярним виразом $a^\ast b(a|b)^\ast$.

В автоматі залишилося лише два стани, тому алгоритм завершується. На переході стоїть шуканий регулярний вираз.

Джерела