Jazyky a překladače - 2 (regulární výrazy a konečné automaty)

2. 8. 2006 | Michal Vyskočil | Programování | 15514×

Jak jsme si ukázali v minulém díle, regulární jazyk je věta generovaná gramatikou typu 3 podle Chomského klasifikace gramatik — gramatikou regulární. V dnešním díle si poodhalíme tajemství těchto mocných nástrojů. Rozdílem oproti minulému dílu bude méně teorie a více praxe.

Obsah

• Co je to regulární výraz
• Implementace regulárních výrazů
• Konečný automat
• O algoritmech převodu
• Závěr

Co je to regulární výraz

Na regulární výrazy existuje několik pohledů. Pro ty, kteří je používat neumí, se jedná o magickou sekvenci znaků, které se nikdy nesnaží porozumět. Pro ty, kteří je používají, se jedná o mocný nástroj pro práci s textem, který lze použít při hledání, pro úpravy, nebo pro ověření vstupního řetězce. No a pro ty, kteří něco vědí o teoretické informatice, se jedná o větu jazyka typu 3. Navíc ta poslední skupina lidí tuší něco o konečném automatu a jeho vztahu k regulárním jazykům, výrazům.

Pochopitelně se nám tu vynořuje otázka. Pokud jsou regulární výrazy výsledkem gramatiky typu 3, to znamená nejméně mocné formy, proč se jimi vůbec zabývat? Proč nenasadit rovnou prostředky klasického programovacího jazyka, který je nepochybně mocnější a zvládne více věcí? Důvodů je několik. Předně síla jazyků typu 3 na většinu úloh stačí (a navíc současné výrazy u moderních nástrojů už patří do vyšších typů). Druhým důvodem je stručnost a (ne)přehlednost zápisu, oproti programové implementaci (jak se přesvědčíte dále). Kniha Art Of Unix Programming se v osmé kapitole zabývá minijazyky pro řešení specializovaných úloh, mezi něž se řadí i regulární výrazy. Obvykle je jednodušší napsat regulární výraz, než vytvořit jeho programovou implementaci.

Implementace regulárních výrazů

Snad každého někdy napadlo — Jak to ten grep (sed, perl, ...) vlastně dělá? Jaká je posloupnost kroků od zadaného výrazu až po kód, který jej provádí? Vezměme jednoduchý výraz x*y+, který značí vezmi libovolný počet znaků x, následovaný alespoň jedním znakem y.

Člověk, který o regulárních výrazech neslyšel, by pravděpodobně začal daný problém řešit asi takto:

function hledej1(inp)
{
byloX = false;      // promenne udavajici
byloY = false;      // stav resene ulohy
zac = 0;
kon = 0;
for (i = 0; i != inp.length; i++) {
  ch = inp.charAt(i);
  if (!byloX && !byloY && ch != "x" && ch != "y") { continue; }
  if (!byloX && !byloY && ch == "x") { byloX = true; zac = i; }
  if (!byloX && !byloY && ch == "y") { byloY = true; zac = i; }
  if ( byloX && !byloY && ch == "y") { byloY = true; }
  if ( byloX &&  byloY && ch != "y") { break;}
  kon++;
}
msg1 = "hledej1(\""+inp+"\") --> x*y+ ";
msg3 = "\n";
if (!byloY) { msg2 = "nenalezen"; }
else        { msg2 = "nalezen (" + zac + ", " + kon + ")";}
return msg1+msg2+msg3;
}

Dlouho jsem přemýšlel, jaký jazyk zvolit pro příklady — C, C++, Javu, Python? Nakonec jsem se rozhodl pro Javascript a to z toho důvodu, že všechny příklady jsou jednoduché a navíc mohou být spuštěny přímo v prohlížeči. Bohužel mi dalo trochu práce ladění, protože se zdá, že některé konstrukce v jistých prohlížečích nepracují, jako třeba foreach (Opera, MSIE) a indexování řetězců (MSIE). Nicméně skripty jsou úspěšně otestovány v prohlížečích Mozilla Firefox 1.5, Internet Explorer 6.0 a Konqueror 3.5 a Opera 9.0. Výsledek (dynamicky generovaný Javascriptem) máte zde:

Zadejte sem vlastní řetězec:

Je nutné poznamenat, že tento způsob implementace je velice (velice jemně řečeno) nevhodný. Kód je zmatený, složitý, špatně se chápe a tím poskytuje prostor pro chyby (ostatně moje implementace pracuje špatně). Navíc, byť i jednoduchá změna, znamená, že je nutné celý program změnit.

Konečný automat

Tím, co kód znepřehledňuje nejvíc, jsou stavové proměnné. Respektive jejich složité vztahy, které musíme v programu uhlídat pomocí složitých podmínek. Pokud se nám v kódu (v lepším případě v návrhu) podobné věci množí, bývá konečný automat nejvhodnějším řešením. Formálně je (nedeterministický, bude vysvětleno dále) konečný automat pětice M = (Q, Σ, δ, q₀ ∈ Q, F ⊂ Q)

• Q je konečná neprázdná množina stavů
• Σ je konečná neprázdná vstupní abeceda
• δ je přechodová funkce (množina pravidel, které popisují přechody mezi stavy ve tvaru δ: Q×Σ→2^Q)
• q₀ ∈ Q je počáteční stav
• F u Q je množina koncových stavů

Nejdůležitějším pojmem u konečného automatu je stav. Koneckonců se někdy nazývají stavovými automaty (Finite State Automata v angličtině). Automat lze graficky znázornit:

Jak vidíte, automat se sestává se 3 stavů S, X a Y, přičemž S je startovacím stavem a Y koncovým. Ne náhodou je tento automat ekvivalentní regulárnímu výrazy x*y+. Ve startovacím stavu S automat čeká na některý ze znaků x, nebo y. V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak y. Potom se přepne do stavu koncového stavu Y. Znak ¬y značí cokoliv mimo y, takže se ze stavu X můžeme dostat do počátku. Praktická implementace by mohla vypadat takto (přidal jsem 4. stav F, abych nemusel používat goto, nebo cyklus while):

function hledej2(inp)
{
states  = {
	S : 0,
	X : 1,
	Y : 2,
	F : 3
}
st = states.S;
zac = kon = 0;

for (i = 0; i != inp.length; i++) {
	ch = inp.charAt(i);
	switch (st) {	case states.S:
		if (ch == "x") { st  = states.X; zac = i;}
		if (ch == "y") { st  = states.Y; zac = i;}
		break;
	case states.X:
		if (ch == "y")      { st  = states.Y; }
		else if (ch != "x") { st  = states.S; }
		break;
	case states.Y:
		if (ch != "y")      { kon = i - 1; st = states.F;}
		break;
	default:
		break;
	};
	kon++;
	if (st == states.F) { st = states.Y; break;}
}

msg1 = "hledej2(\""+inp+"\") --> x*y+ ";
msg3 = "\n";
if (st != states.Y)     { msg2 = "nenalezen";}
else                    { msg2 = "nalezen (" + zac + ", " + kon + ")";}
return msg1+msg2+msg3;
}

Zadejte sem vlastní řetězec:

Tato, byť na počet řádků delší, ale jednoznačně přehlednější implementace konečného automatu, je přesně to, co mnoho programátorů s úspěchem používá. Je nutné říct, že takto natvrdo naprogramovaný stroj trpí špatnou rozšiřitelností, ale místo konstrukce switch case lze z výhodou použít hashovací pole.

Ovšem i toto řešení trpí malou obecností. Pokud chceme změnit regulární výraz, nezbude nám, než kód přeprogramovat (anebo použít dynamické jazyky a hashovací pole místo konstrukce case). Ovšem je tu ještě jedna možnost - jiný pohled na konečné automaty a to tabulka přechodů. Prakticky stejně jsou implementovány všechny pomocné knihovny pro konečné automaty.

Stav	S	X	Y
x	X	X	S
y	Y	Y	Y
...

O algoritmech převodu

Ještě než budeme pokračovat, zbývá nám vysvětlit jeden pojem. Deterministický (DKA), versus nedeterministický automat (NKA). U DKA je přechod jednoznačně dán příští stav aktuálním stavem a podmínkou. NKA může mít na jednu podmínku následujících stavů více. Oba automaty jsou ekvivalentní, ale nedeterministické jsou rychlejší, protože nemusí prohledávat všechny možnosti a vyberou si vždy správnou větev. Nevýhodou je, že naše počítače, jak je známe dnes, jsou deterministické, což znamená, že nedeterministické stroje se stejně musejí převést na deterministické. Fragment NKA je zobrazen na následujícím obrázku.

Mluvím o tom z toho důvodu, že běžně používaný algoritmus převádí regulární výrazy právě na NKA. Pokud se narazí na větev, která vede na více možností, program začne prozkoumávat jednotlivé cílové stavy (backtracking). Klasický postup skončí v případě nálezu prvního vyhovujícího výrazu. Posixová varianta v případě použité konstrukce "nebo" najde všechny vyhovující a vrátí nejdelší řetězec, ale tuto variantu běžné nástroje neimplementují, protože je nejpomalejší. Druhou možností je paralelní provádění všech cest, díky čemuž stačí jeden průchod a není třeba se vracet. Nevýhodou je skutečnost, že si nemůžete zapamatovat podvýrazy.

Závěr

Toto byl pouze lehký úvod do problematiky konečných automatů. Zcela jsem vynechal problematiku stavových akcí, pojmy jako Mealy a Moorův automat. Nemluvili jsme o greedy regulárních výrazech a podobně. Navíc jsem tvorbu stroje pro provádění regulárních výrazů lehce odbyl. Jednak dnešní nástroje obecně regulární výrazy podporují. A v případě, že ne, je nejlepším způsobem jednoduše použít knihovnu PCRE (Perl Compatible Regular Expressions), která je syntakticky i sémanticky kompatibilní s regulárními výrazy Perlu. Což je defakto norma, protože skutečná norma POSIX se používá méně a její regulární výrazy nejsou tolik silné. Tuto knihovnu používají open source projekty Exim (pro nějž byla původně napsána), Apache, PHP, Postfix, nebo KDE.

Pokud chcete automaty vidět na vlastní oči, podívejte se na Animace Teoretické informatiky, jedná se o flashové animace konečných (DKA i NKA) automatů, převodů NKA na DKA a mnoho dalších zajímavých věcí.

V dalším díle se zvolna přesuneme k problematice překladačů, na řadě je totiž syntaxe.

       

Komentáře

[diverman]

V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak y

V tom případě máš drobnou chybku v obrázku u svislé šipky ze stavu X do Y.

[diverman]

takto? Jinak ta tabulka přechodů mi taky moc nesedí, podle ní bych po přečtení x měl jít ze stavu Y do S, což ale neodpovídá obrázku...

[Radek Hladik]

Neoznačuje se kolečkem koncový stav? Podle mně je koncový ten stav Y a ne S...

Radek

[Radek Hladik]

Ze školy si matně vzpomínám na algoritmus, který RE převáděl přímo na minimální deterministický automat. Používala se tam derivace regulárních výrazů a bylo to vcelku elegantní.

Radek

[Kyosuke]

hledej1("y") --> x*y+ nalezen (0, 1)

To je velmi optimistický výsledek... Nemělo by to na osamocené „y“ mlčet?

[Kyosuke]

Á, nemělo, já bych měl mlčet a jít spát. V tuhle noční hodinu mi vypadl z hlavy význam hvězdičky. No jo, dobrou a díky... Přečtu celé, až budu v použitelném stavu...

[Radek Hladik]

Ne, protože x* znamená libovolný i nulový počet výskytů x, zatímco y+ znamená nenulový počet výskytů. Proto y sedí, ale třeba osamocené x by nesedělo.

Radek

[Kyosuke]

Viz moje „odpovím si sám“ o kousek výše...

[mmm444]

Pro ukázku, jak vypadají a pracují automaty pro regulární výrazy, doporučuju navštívit http://osteele.com/tools/reanimator/ .

[kralyk z abclinuxu]

to je pekne...
napsal sem tam "(a*|b*)|(s*a)|(\d\w|d*)|(a*b|b*a)|(([a-d]\d|[a-d]\w)(a*b|b*a)([a-d]*\d))" a musel sem zvetsit rozliseni
ale graf je to peknej...

[xvasek]

Vidím, že si autor vzal z minulé diskuse pod článkem pár věcí. Tady toto pokračování je mnohem lepší matroš, hned sem pár lidí pošlu.

Ještě by mě zajímalo, co je to "věta" (zmiňovaná v perexu a ještě v článku), já znám jenom písmeno (nebo symbol) a pak už jenom jazyk.

[Radek Hladik]

Věta nebo taky slovo nebo řetězec jsou výrazy pro libovolnou kombinaci písmen abecedy. Pokud pak mám nějaký jazyk, pak se většinou říká "věta z jazyka" nebo "slovo z jazyka". Říká se "slovo xyyy do jazyka L patří", zatímco "slovo xxyx do jazyka L nepatří".

Řetězec je v principu totéž, jen se používá tam, kde není potřeba uvažovat o příslušnosti k jazyku. Například: "Vezměme všechny třípísmené řetězce nad abecedou {x,y}, potom vezměme všechna slova vzniklá kombinací právě dvou takovýchto řetězců a zjistíme, která z nich spadají do jazyka L."

Radek

[xvasek]

Aha, takže věta = slovo?

[happy barney]

veta = postupnost slov patriacich do jazyka.

[Marek Bernát]

Áno a nie. Jedná sa tu o nejednoznačnosť v definíciách. AFAIK informatici používajú výrazy (abeceda, znak, slovo) a lingvisti zasa (slovník, slovo, veta). Teda, to čo ste napísali vy, by v klasickej informatickej definícií znelo "slovo = postupnost znakov patriacich do jazyka." Myslím, že používať obe definície zároveň je zbytočné a veľmi mätúce.

[vogo]

Co třeba nějak formálně zmínit Kleenyho větu o korespondenci regulárního výrazu a konečného automatu :), něco jako: "Libovoný jazyk je popsatelný regulárním výrazem právě tehdy když je rozpoznatelný konečným automatem." + názorně ukázat jak se přechody v automatu nahrazují elementárními regulárními výrazy.

[pcman]

Mala nepresnost. Jazyk neni veta. Jazyk (nad abecedou X) je lib. podmnozina uzaveru (nad abecedou X).

[David Široký]

Zdravím!

Nevim, jak přesně funguje program grep, ale určitě nevytváří žádný NKA nebo DKA. Většina implementací regulárních výrazů kompiluje výrazy do instrukcí zásobníkového procesoru, který zvládá i proměnné a rekurzivní volání, a tím se pak zpracovává předložený text.

Pro jednu firmu jsem vypracovával knihovnu, která převádí regulární výrazy na DKA. U mnoha výrazů je to hračka a otázka milisekund, ale narazili jsme i na případy, kdy převod potřeboval stovky megabajtů paměti a trvalo to celý den. Jednoduchým příkladem budiž např. výraz "a{0,100000}". Jen adekvátní NKA by měl kolem 100000 stavů a dvojnásobek hran a vytvoření DKA by nějakou tu chvíli zabralo. Nebo jsme narazili na výraz, ze kterého lze vytvořit poměrně jednoduchý NKA, ale komplexnost DKA rostla exponenciálně. Pokud bude někdo chtít, tak tyhle "zrůdné výrazy" zkusim najít

David

[peter_h]

Hej, prevod NKA na DKA zacne byt zaujimavy ked to clovek robi rucne na papieri .

[Radek Hladik]

A jeste k tomu na to ma 10 minut a musi to bejt spravne :)

Radek

[lankvil]

Moc pekny clanek, jak funguje grep me vzdycky zajimalo.

Jenom tenhle kus kodu mi prijde nejaky podezrely. javascript neznam, ale misto toho prvniho break bych videl radsi case ;)

	break states.Y:
		if (ch != "y")      { kon = i - 1; st = states.F;}
		break;

[Michal Vyskočil]

Díky za upozornění

[kralyk z abclinuxu]

Mam pocit ze v tom prvnim grafu je chybicka ... u toho bodu X by ta sipka co vede k bodu Y mela by nazvana y ane x. Aspon si to myslim...dyztak me opravte...

[kralyk z abclinuxu]

aha dobry uz sem to pochopil von je to NKA sorry za blbou pripominku...

[Lukáš Rýdlo]

Pekny clanek -- rad si s nim zopakuju, co jsem za ten rok od zkousky z formalu a automatu zapomnel . Jen drobnost: pokud me pamet nesali, tak u prvniho obrazku urcite neni koncovy stav Y, ale S, protoze v grafu se pocatecni stav oznacuje "sipkou odnikud do stavu" a koncovy (akceptujici) "dvojitym koleckem", takze na tom obrazku je S pocatecni a zaroven koncovy stav...

A pokud si chce nekdo trochu pohrat, doporucuju stahnout pekny simulator automatu v Jave ze stranek http://ozark.hendrix.edu/~burch/proj/autosim/

[klobouk]

Obrazky, priklady, funkcni okenko na vyzkouseni ... to je naprosto super tahak pro lidi co tomu nerozumi (jako treba ja) a chteji se neco dozvedet A navic je to proste bajecne nazorne. Je to parada.

Jen bych se mozna primluvil za to, aby uvadene priklady byly spravne. Sice jsem si s prvni implementaci x*y+ hral, ale zrovna mne nenapadla kombinace, na ktere je chyba tehle implementace videt a z toho kodu jsem to taky nejakou dobu musel lustit nez jsem prisel na to co je blbe a jak to (mozna, nemam overeno) udelat spravne. Popravde, kdyby to autor nezminil, tak bych na chybu sam od sebe asi neprisel.

Jinak mam teda par laickych dotazu:

Ad sipka X, Nechapu proc je v prvnim obrazku (SXY) u prechodu X->Y sipka oznacena X, a to ani po upozorneni Kralik_, ze je to NKA (coz si nejsem moc jisty). Podle "selske" logiky bych tam dal Y. Jsem ve stavu X, kdyz narazim na dalsi X, tak zustavan ve stavu X (kruhova sipka k X oznacena X), kdyz narazim na cokoliv jineho krome X a Y tak jdu zpet do S (sipka k S oznacena !y, coz je skoro jako S ) a pokud narazim na Y tak jdu ze stavu X do stavu Y (sipka oznacena X?!, to mi spis sedi Y, jak navrhoval diverman v druhem prispevku).

Dotaz 1: proc je tam X ?

Ad NKA, na mne to schema spis pusobi pomerne "urcite" co se tyce pravidel pro prechody mezi stavy. Pokud neco, tak bez touto a jenom touto cestou tamhle.

Dotaz 2: proc by to mel byt NKA ?

Ad konecny stav, pochopil jsem notaci, ze sipka od nikud do stavu oznacuje start a dvojite kolecko oznacuje konecny stav. Coz zjevne vypada jak bylo zmineno vyse, ze zacatek je shodny s koncem. Dava to v teto uloze smysl ?

Dotaz 3: kde je teda konecny stav ? A pokud je v S tak proc ?

Ad prechodova tabulka, jasne a pochopitelne az na nezodpoveznou poznamku divermana o prechodu Y->S po precteni x

Dotaz 4: jdu skutecne do ... S po precteni x ve stavu Y ? Pokud ano, melo by to byt v obrazku ?

Ad

ostatně moje implementace pracuje špatně

Pomohla by pridat pred posledni podminku jeste jednu ? if ( byloX && !byloY && ch != "y") { byloX = false; zac = 0; kon = 0;}

Dotaz 5: Opravil by muj navrh na pridani podminky tu implementaci ?

Diky moc za pripadne odpovedi a srry za takovou zbesilou tapetu, ale pro lidi co nemaji potrebnou vysokou skolu je dobre, kdyz se i v trivialitach ujisti. Je to lepsi nez stavet na necem co je blbe

[Lukáš Rýdlo]

Hmm, vsechny dotazy asi nezodpovim, ale alespon neco: To x nad sipkou ze stavu X do Y je samozrejme spatne -- patri tam y (to je to alespon jedno y, ktere tam musi byt kvuli +). NFA je to proto, ze z jednoho stavu vede vice sipek s x. To je ten nedeterminismus. Konecny automat cte ze vstupni pasky jednotliva pismenka a kdyz dorazi do stavu X a zrovna ma cist dalsi pismenko x, tak nevi, kudy ma jit. Pokud by byl ten obrazek spravne (viz vyse), bude ten automat DFA (deterministicky), protoze v zadnem ze stavu neni moznost jit vice jak jednou cestou skrze jeden znak.

Koncovy stav je samozrejme Y. Lepsimu pochopeni by prispel uzivanejsi termin (aspon u nas na FI MUNI ) "akceptujici stav". Tento stav neni vyjimecny tim, ze se v nem vypocet zastavi, jak by mohlo napovidat slovo "koncovy", ale tim, ze pokud dojdou pismenka na vstupni pasce a automat je zrovna v tomto stavu, pak je slovo "akceptovano", tedy uznano za spravne. Pokud by dosla pismenka a automat byl v jinem stavu, nez v nekterem z akceptujicich, je slovo zamitnuto, tedy prohlaseno za spatne. Pekne je to videt pri simulaci v tom simulatoru, co jsem dal odkaz vyse.

Ad 4: Ve stavu Y smim cist jen znaky y. Spravne by mel mit automat jeste jeden neakceptujici stav (jednoduche kolecko), kam by byl automat "nasmerovan", pokud by ve stavu Y precetl cokoliv jineho nez y. Sipka not(y) do S je taky zbytecna, protoze predpokladam, ze mame abecedu {x,y}, takze not(y) je x a pod tim se cykli nad X (prechod do S vnasi jen nedeterminicnost a vynucuje dve x za sebou). Pokud mel autor na mysli "sirsi" abecedu, pak ma not(y) jit do zmineneho noveho neakceptujiciho stavu, protoze slova obsahujici jakykoliv jiny znak nez x a y neodpovidaji x*y+. Navic prechod do S umoznuje akceptaci slov jako treba xzxy, coz jiste neodpovida x*y+, tedy pokud se bavime o automatech a ne o vyhledavani retezce x*y+ v nejakem jinem retezci. To take implikuje, ze z Y pod x rozhodne nejdeme do S. Umoznili bychom akceptaci napr. slova xyxy a to neodpovida x*y+, ackoliv tento "patern" obsahuje hned dvakrat. Samozrejme je tu opet ona nejasnost, jestli se bavime o automatech nebo o implementaci vyhledavani regularnich vyrazu v retezci za pouziti automatu. Ze clanku mi to neni zcela jasne.

Y je koncovy stav proto, ze pokud jsme v nem, mohli jsme projit lib. poctem pismen x a alespon jednim y (at uz to y bylo bez x nebo ne).

A jestli by ten navrh opravy neco spravil se mi opravdu ted nechce zjistovat. Ten kod je totalne necitelny, jak pravil koneckoncu i autor

[klobouk]

To x nad sipkou ze stavu X do Y je samozrejme spatne -- patri tam y (to je to alespon jedno y, ktere tam musi byt kvuli +). NFA je to proto, ze z jednoho stavu vede vice sipek s x. To je ten nedeterminismus. Konecny automat cte ze vstupni pasky jednotliva pismenka a kdyz dorazi do stavu X a zrovna ma cist dalsi pismenko x, tak nevi, kudy ma jit. Pokud by byl ten obrazek spravne (viz vyse), bude ten automat DFA (deterministicky), protoze v zadnem ze stavu neni moznost jit vice jak jednou cestou skrze jeden znak.

Njn, pokud je nad sipkou "y" a pokud not(y) znamena cokoliv jineho krome x a y, pak nepovede z jednoho kolecka vice sipek ze stejnym pismenkem => je to spis DKA podle toho co rikas.

Pokud ale not(y) zahrnuje i moznost "x" (bezohledu na to, ze tato moznost uz je tam konkretne zminena tou kruhovou sipkou), pak opravdu bude kolecko X s vice stejnymi moznostmi "uniku" a pak je to jednoznacne NKA jak pises.

A pokud by byl obrazek spravne tak by opet bylo vice stejnych vetvi s jednoho kolecka a pak by to spis byl NFA ne ?

Ted mi teda zbyva otazka, jak je to s tim not(y) v tomto pripade ?

PS: jinak ostatni bylo velice pochopitelne napsano, diky :-}

[Lukáš Rýdlo]

Koukam, ze jsem to s tou opravenou a neopravenou verzi trochu zamichal . Nuze k tomu "not": nejak si nevybavuju, ze bychom ho vubec v automatech pouzivali. Kazdopadne bych to not intuitivne definoval tak, jak to byva obvykle, tedy not(y) je vsechno krome y (nezavisle na jinych sipkach do jinych stavu). Spis si vybavuji, ze jsme nad sipku vypisovali vsechny znaky, pod kterymi se do daneho stavu prechazi. Je to proto, ze se automaty vetsinou probiraji nad nejakou "malou" abecedou, napr. {x, y} nebo {a, b, c, d}, aby to bylo nazorne a prehledne. U toho obrazku postradam exaktni definici abecedy, nicmene pokud jsme si ve cvikach abecedu nedefinovali, vzdycky jsme pocitali s tim, ze abeceda ma jen pismenka obsazena v grafu. Proto je to "not" ponekud nelogicke. Pri abecede {x,y} je not(y)=x. Pokud ma mit abeceda vice pismen, pak chybi definice (a navic jsou pro tuto ulohu jina pismena zbytecna).

A ted k te determinite:

Tak jak je to v obrazku je to jednoznacne NEDETERMINISTICKE (NFA) a to kvuli stavu "X". Z nej vede smycka pod x, sipka do Y pod x a sipka do S pod not(y), coz je take x.

Pokud obrazek opravime, odstranime not(y), ktere je chybne, a zamenime x za y v preklepu pri prechodu z X do Y, pak je to DFA, protoze z S jde po jedne sipce pod x a pod y, z X jde smycka pod x a sipka pod y a z Y je jen smycka y. Nikde tedy neni vic jak jedna sipka z jednoho stavu pod stejnym znakem. (Samozrejme tou opravou myslim opravu chyb v obrazku a ne algoritmicky postup, jak prevest NFA na DFA.)

[klobouk]

jop, s tim naprosto souhlas

[ldx]

Tenhle clánek doporucím neználkum vyrostlým na win platforme jako úvod do regulárních výrazu. Proto jsem zvedav, jestli se dockám nejaké finální verze s opravenými chybami, doplnené na základe probehlé diskuze

[ehmmm]

Neznalek z Windows po temer 10 letech dorazil. Rekl bych, ze chyby tu jsou stale. Zrejme jako domaci cviceni pro pozorne ctenare. Jeste navic u toho javascriptu se stavovym automatem bych radek kon++; posunul az za if ... states.F ... break;

Rozhodne ale je tento dil vyrazne praktictejsi a tim padem stravitelnejsi nez dil prvni. Autorovi a diskutujicim dekuji.