Nedeterministický konečný automat

M=({q0,q1,q2,q3},{0,1},,q0,{q1,q3})

L(M) = ?

Nedeterministický konečný automat

Nedeterministický konečný automat (NDKA) je obecnějším typem konečného automatu

Rozdíl oproti deterministickému konečnému automatu (DKA) spočívá v tom, že aktuální vnitřní stav a čtený symbol neurčují jednoznačně chování automatu v dalším kroku (tj. stav, do kterého automat má přejít)

Namísto přechodové funkce budeme tedy uvažovat přechodové zobrazení

Prakticky si tuto změnu můžeme představit tak, že NDKA má možnost „si vybrat“ z nabízených možností přechodu

V předchozím příkladu může tedy automat ze stavu q0 na vstupní symbol 1 přejít do q1 nebo do stavu q2

Nedeterministický konečný automat

DEF: Nedeterministický konečný automat M je pětice M=(Q,T,,q0,F), kde

Q je konečná množina vnitřních stavů automatuT je konečná množina přípustných vstupních symbolů je přechodové zobrazení : QxT 2Q

q0 je počáteční stav automatu (q0Q)

F je množina koncových stavů (FQ)

Poznámka: 2Q je symbolické označení množiny všech podmnožin Q Jestliže Q={a,b}, potom 2Q ={{},{a},{b},{a,b}}

Užívané konvence a pojmy

DEF: Buď M=(Q,T,,q0,F) nedeterministický konečný automat (NDKA). Potom nad množinou všech konfigurací QxT* definujeme relaci přechodu následovně:jestliže q1,q2Q, wT*, aT, potom

(q1,aw) (q2,w), jestliže q2(q1,a)

DEF: Nechť M=(Q,T,,q0,F) je NDKA.

Potom automat M přijímá (akceptuje) slovo wT*, jestliže platí

(q0,w) * (q,e) pro nějaké qF.

DEF: L(M)={w| (q0,w) * (q,e), wT*, qF}.

Příklad

Uvažujme následující NDKA reprezentovaný stavovým diagramem:

M=({q0,q1,q2}, {+,-,0,1,2,3,4,5,6,7,8,9}, , q0,{q2})

Příklad

Tentýž NDKA lze reprezentovat následující přechodovou tabulkou:

M=({q0,q1,q2}, {+,-,0,1,2,3,4,5,6,7,8,9}, , q0,{q2})

+ | - 0|1|2|…|9q0 {q1} {q1, q2}

q1 - {q1, q2}

q2 - -

Přijímaní slova pomocí NDKA

M=({q0,q1,q2}, {+,-,0,1,2,3,4,5,6,7,8,9}, , q0,{q2})

Pro vstupní slovo w=-195 probíhá následující výpočet:(q0,-195) (q1,195) (q1,95) (q1,5) (q1,e) … nepřijato

(q2,e) … přijato

(q2,5) … nepřijato

(q2,95) … nepřijato

+ | - 0|1|2|…|9q0 {q1} {q1, q2}

q1 - {q1, q2}

q2 - -

Přijímaní slova pomocí NDKA

Výpočet NDKA si lze představit jako odpovídající množství paralelně probíhajících výpočtů

Kdykoliv může NDKA učinit rozhodnutí (není jednoznačně určen následující stav), vzniká další větev výpočtu

Větev výpočtu je ukončena (zaniká), pokud vstupní slovo bylo celé přečteno, nebo když nelze pokračovat (není definován přechod pro daný vnitřní stav a čtený symbol)

NDKA přijímá dané vstupní slovo právě tehdy, když alespoň jedna větev výpočtu skončí úspěchem (přečtené celé slovo & automat je v některém z koncových stavů)

Vzájemný vztah DKA a NDKA

NDKA se na první pohled zdá „mocnější“ než DKA

Jakým způsobem měřit „sílu“ jednotlivých typů automatů?

Automaty jsme navrhli kvůli rozpoznávání jazyků, a proto i jejich schopnosti budeme posuzovat podle množiny jazyků, které lze daným typem automatu rozpoznat

Věta: Nechť L(M1) je jazyk přijímaný nějakým nedeterministickým konečným automatem. Potom existuje deterministický konečný automat M2, který přijímá stejný jazyk, tj. L(M1) = L(M2).

Důkaz: M2 se sestrojí na základě znalosti funkce M1

Konstrukce ekvivalentního DKA

M1=({q0,q1,q2}, {+,-,0,1,2,3,4,5,6,7,8,9}, , q0,{q2})

M2=({?????}, {+,-,0,1,2,3,4,5,6,7,8,9}, 2, {q0},{?????})

Budeme postupně vytvářet 2 i Q2 a nakonec určíme F2

+ | - 0|1|2|…|9q0 {q1} {q1, q2}

q1 - {q1, q2}

q2 - -

Konstrukce ekvivalentního DKA

M2=({?????}, {+,-,0,1,2,3,4,5,6,7,8,9}, 2, {q0},{?????})

+ | - 0|1|2|…|9

q0 {q1} {q1, q2}

q1 - {q1, q2}

q2 - -

2 + | - 0|1|2|…|9

{q0} {q1} {q1, q2}{q1} - {q1, q2}

{q1, q2} - {q1, q2}

Konstrukce ekvivalentního DKA

formální

přeznačení

M2=({p0, p1, p2}, {+,-,0,1,2,3,4,5,6,7,8,9}, 2, p0, {p2})

2 + | - 0|1|2|…|9

{q0} {q1} {q1, q2}

{q1} - {q1, q2}

{q1, q2} - {q1, q2}

2 + | - 0|1|2|…|9

p0 p1 p2

p1 - p2

p2 - p2

Konstrukce ekvivalentního DKA

M2=({p0, p1, p2}, {+,-,0,1,2,3,4,5,6,7,8,9}, 2, p0, {p2})2 + | - 0|1|2|…|9

p0 p1 p2

p1 - p2

p2 - p2

Konstrukce ekvivalentního DKA

NDKA: M1=({q0,q1,q2}, {+,-,0,1,2,3,4,5,6,7,8,9}, , q0,{q2})

DKA: M2=({p0,p1,p2}, {+,-,0,1,2,3,4,5,6,7,8,9}, 2, p0, {p2})

L(M1) = L(M2)

Konstrukce ekvivalentního DKA

Shrnutí postupu konstrukce:Vyjdeme z počátečního stavu NDKA – stav {q0}Postupně použitím přechodového zobrazení

vyplňujeme přechodovou tabulku Jednotlivé množiny nově vznikajících stavů považujeme

vždy za jeden stav nově konstruovaného automatuTyto stavy postupně dáváme do prvního sloupce tabulky

a opět pro ně vyplňujeme přechodovou tabulku Všech možných podmnožin je 2|Q|, a proto po konečném

počtu kroků skončíme (nová množina stavů již nevznikne)

Všechny podmnožiny obsahující alespoň jeden koncový stav původního NDKA prohlásíme za koncové stavy DKA

Konstrukce ekvivalentního DKA

Tento postup je zcela obecný a realizovatelný pro každý nedeterministický konečný automat

Formální zápis tohoto postupu je důkazem dříve uvedené věty o ekvivalenci NDKA a DKA

Důsledky:NDKA i DKA přijímají stejné jazyky, tj. zobecněním

DKA na NDKA se příslušná třída jazyků nezměníPodle toho, co nám v praxi bude vyhovovat, můžeme

pracovat s DKA nebo NDKA, protože víme, že rozlišovací schopnost obou typů je stejná

Příklad 1

NDKA: M1=({q0,q1,q2,q3},{0,1},,q0,{q1,q3})

DKA: M2= ?

L(M1) = L(M2) = ?

Příklad 2

NDKA: M1=({q0,q1,q2,q3},{0,1},,q0,{q3})

DKA: M2= ?

L(M1) = L(M2) = ?

0 1

q0 {q0,q1} {q0,q2}

q1 {q1,q3} {q1}

q2 {q2} {q2,q3}

q3 - -

Další úlohy na automatech

Rozpoznávací experiment – nalezení nejkratšího slova, které rozlišuje dva různé stavy

Synchronizační problém – dovedení automatu z neznámého do konkrétního stavu

Nalezení redukovaného automatu (automat rozpoznávající tentýž jazyk s minimálním počtem stavů)- odstraní se nedosažitelné stavy- odstraní se nerozlišitelné stavy

Vztah KA a regulárních gramatik

Věta: Nechť G=(N,T,P,S) je regulární gramatika. Potom existuje konečný automat M=(Q,T, , q0,F) takový, že L(M)=L(G).

Důkaz: konstrukcí KAQ=N{A}, AN (tj. nový symbol)

T=Tq0=S

F = {S,A} pokud Se je pravidlo z P, jinak F = {A}: Pro Ba P definujeme A (B,a)

BaC P definujeme C (B,a)a v ostatních případech Ø = (B,a)

Vztah KA a regulárních gramatik

Důkaz: 1) Je třeba dokázat, že ke každé derivaci S G w lze

sestrojit odpovídající posloupnost přechodů (S,w) …. (A,e) Potom L(G) L(M)

2) Je třeba dokázat, že ke každé posloupnosti přechodů (S,w) …. (A,e) existují příslušná přepisovací pravidla a lze tedy sestrojit odpovídající derivaci S G w

Potom L(M) L(G)

Z čehož plyne: L(G) = L(M) cbd.

Vztah KA a regulárních gramatik

Důsledek: Jelikož konečné automaty rozpoznávají věty regulárního jazyka, stávají se přirozenými modely analyzátorů překladačů.

Na základě právě uvedené věty je možné lexikální analyzátor zkonstruovat automaticky z popisu regulární gramatiky.

Na této větě je založena automatizace vybraných částí překladače a je to tedy věta nesmírně užitečná.

Příklad 3

Mějme gramatiku G=({C,D},{+,-,0,1,…,9},P,C), kde

P = {C +D | -D | 0 | 1 | … | 9 | 0D | 1D |…| 9DD 0 | 1 | … | 9 | 0D | 1D | … | 9D }

KA = ?L(G) = ?

Vztah KA a regulárních gramatik

Věta: Nechť M=(Q,T, , q0,F) je konečný automat. Potom existuje taková regulární gramatika G=(N,T,P,S), že L(M)=L(G).

Důkaz: konstrukcí gramatiky z DKA (stačí pro DKA)N = QT = TS = q0

a P je definována následovně: BaC P jestliže (B,a) = CBa P jestliže (B,a) = K F

Se P jestliže q0 F

Příklad 4

Ke konečnému automatu M=({q0,q1,q2,q3},{0,1},,q0,{q0})

najděte takovou regulární gramatiku G, aby platilo L(M)=L(G).

0 1q0 q2 q1

q1 q3 q0

q2 q0 q3

q3 q1 q2

Vztah KA a regulárních gramatik

Věta:

Jazyk L je regulární právě tehdy, když

je rozpoznatelný konečným automatem.

Souhrnná formulace obou dříve formulovaných vět.

Vztah KA a regulárních gramatik

Důsledek: Na základě obou zde uvedených vět je zřejmé, že regulárními gramatikami i konečnými automaty popisujeme naprosto identickou množinu jazyků.

Rozdílný charakter popisu (generování vs. rozpoznávání vět jazyka) umožňuje ke stejnému jazyku přistupovat z různých hledisek a podle potřeb praxe

Z aplikačního hlediska je velice cenná věta první (ke gramatice automaticky najdu automat), druhá věta se tolik v praxi nevyužívá

Vlastnosti regulárních jazyků

Věta: Nechť L1 a L2 jsou regulární jazyky. Potom

L1 L2 , L1 L2 , T*\L1 a L1•L2 jsou také regulární jazyky.

Důkaz:L1 L2 … dva automaty vedle sebe a stačí jeden úspěšný

L1 L2 … dva automaty vedle sebe a oba úspěšné

T*\L1 … stačí udělat F`= Q\F

L1•L2 … dva automaty za sebou tak,že v koncovém stavu

prvního automatu je vždy navázán automat druhý

Další příklady konečných automatů

Navrhněte automat přijímající jazyk nad abecedou {0,1}, jehož slova začínají 1 a končí 0

Navrhněte automat přijímající jazyk nad abecedou {0,1}, jehož slova obsahují nejméně tři 1

Navrhněte automat přijímající jazyk nad abecedou {0,1}, který přijímá slova končící sufixem 00

Navrhněte automat přijímající jazyk nad abecedou {0,1}, jehož slova mají na lichých pozicích vždy znak 1

Další příklady konečných automatů

Navrhněte automat přijímající jazyk nad abecedou {a,b}, který přijímá slova nejvýše délky 4

Navrhněte automat přijímající jazyk nad abecedou {a,b}, který přijímá všechna slova kromě aa a aaa

Navrhněte automat přijímající jazyk nad abecedou {a,b}, jehož slova obsahují podřetězec baba

Navrhněte automat přijímající jazyk nad abecedou {a,b}, jehož slova neobsahují podřetězec baba