Од ДКА во Регуларен израз

Теорема. Ако L е јазикот на некој детерминистички конечен автомат А, тогаш L е јазикот на некој регуларен израз R. 

Доказ. Без губење на општоста, да претпоставиме дека состојбите на автоматот А се обележани со природните броеви од 1 до n. Q = {1,2,3,...,n}. Без оглед на тоа колку состојби има автоматот и како се означени, секогаш ќе бидат конечен број и секогаш ќе можеме да ги преименуваме на горенаведениот начин. Нека R(i,j,k) го означува регуларниот израз во чиј јазик влеуваат сите зборови w добиени со конкатенација на симболите долж било кој пат што води од состојба i до состојба j и притоа НЕ поминува низ (меѓу-)состојба поголема од k. Почетната состојба i и крајната состојба j не се меѓусостојби и за нив не важи ограничувањето да се помали од или еднакви на k. Ќе тргнеме од основниот случај кога k=0, постепено ќе го прошируваме множеството состојби низ кои ќе дозволуваме да се поминува тргнувајќи од состојба i до состојба j, за на крај кога k=n ограничувањето воопшто да не постои и да ги добиеме сите регуларни изрази за било кој пар на состојби. 

Основен случај. k = 0. Бидејќи сите состојби се нумерирани од 1 па нагоре, случајот k=0 значи дека по патот од i до j не смее да постои меѓу состојба. Разгледуваме два случаи :

1. i != j. Ова е случајот кога i и j се две различни состојби и потребно е да ги најдеме сите лаци кои водат директно од i до j. Tогаш, R(i,j,0) е унија од сите симболи долж овие лаци. Ако до состојба j не може да се дојде директно од состојба i, т.е. не постои симбол од азбуката со кој се преминува од i во j, тогаш R(i,j,0) е празно множество.

2. i=j. Ова е случајот кога i и ј се всушност една иста состојба. Конструирањето на R(i,j,0) се сведува на горниот случај со таа разлика што регуларниот израз никогаш не може да биде празно множество бидејќи секогаш ќе биде можен епсилон-преминот - бидејќи се работи за една иста состојба.

Формално, R(i,j,0) е унија од сите симболи а од азбуката такви што delta(i,a) = j. Дополнително, ако i=j, тогаш во унијата се додава и празниот збор епсилон.

Индукција. Да претпоставиме дека постои пат од состојбата i до состојбата j кој не поминува низ состојба поголема од k. Тогаш, можни се два случаи :

1. Патот воопшто не поминува низ состојбата k. Во овој случај R(i,j,k) = R(i,j,k-1).

2. Патот поминува низ состојба k барем еднаш. Тогаш, патот може да се подели на три дела. Првиот оди од i до k без да помине низ состојбата k. Вториот дел оди од состојба k до состојба k нула, еднаш, или повеќе пати, без притоа да помине низ состојбата k (затоа што k е и почетна и крајна состојба на овој дел од патот). Третиот дел оди од состојба k до состојба j повторно без да помине низ состојбата k. Во овој случај R(i,j,k) = R(i,k,k-1)R(k,k,k-1)*R(k,ј,k-1). Или : ако одиме од состојба i до состојба j поминувајќи низ состојбата k, тогаш патот можеме да го разгледуваме дека е составен од помали патишта кои НЕ поминуваат низ k и чии регуларни изрази се веќе пресметани.

Комбинирајќи ги овие два случаи, за R(i,j,k) довибаме :

R(i,j,k) = R(i,j,k-1) + R(i,k,k-1)R(k,k,k-1)*R(k,ј,k-1).

На крајот, кога k=n не постои ограничување на состојбите низ кои можеме да поминеме, па регуларниот израз за јазикот на автоматот ќе биде унија од сите регуларни изрази R(1,ј,n) над сите крајни состојби j под претпоставка дека 1 е почетната состојба.

3SEM FoJa Regularen Izraz DKA deterministicki konecen avtomat pretvoranje konverzija