Обобщен недетерминиран краен автомат

Обобщен недетерминиран краен автомат, съкратено ОНКА, е недетерминиран автомат, в чиито преходи може да има не само символи от азбуката, но и регулярен израз.

Определение

ОНКА ще ни трябва по време на алгоритъма за преобразуване на краен автомат в регулярен израз. ОНКА е следователно НКА, който има преходи, зададени с регулярни изрази. Пример за такъв ОНКА:

Виждаме, че например от състоянието q₂ води преход към състоянието q_f и е означен с регулярния израз a^∗ 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. Ако в автомата липсва някакъв преход, който по определение би трябвало да е там, създаваме го и го означаваме с регулярния израз ∅. Така не променяме езика, който автоматът приема, защото такъв преход никога не се извършва.

Този автомат можем да използваме за преобразуване на автомат в регулярен израз.