Jen drobnou pripominku k teto vete vyskytujici se v clanku..."Ze všeho nejdříve si pro něj sestaví konečný (nejlépe deterministický, aby se dobral výsledku) automat."
Tu poznamku v zavorce nechapu. Deterministicke a nedeterministicke konecne automaty jsou ekvivalnentni. Nedeterministicke konecne automaty samozrejme take davaji vysledky (jinak by byly k nicemu), a ke kazdemu nedeterministickemu konecnemu automatu lze sestrojit trivialne deterministicky, ktery je co do prijimanych slov ekvivalentni puvodnimu nedeterministickemu.
Jojo, to je, ale sestevit nedeterm. automat pro regex je trivialni, kdezto determ. uz tak trivialni neni - teda, neni jednoducha implementace, teorie jednoducha je. Taky ma tato transformace jeden docela neprijemny hacek, prevodem z nedet. na det. roste exponencialne pocet stavu. Zkuste si treba vyraz (a|b)*a(a|b)^n, teda posloupnost acek a becek, kde n-ty znak pred koncem je acko. Zjistite, ze pocet stavu determ. automatu je neco kolem 2^n. V praxi se to dela tak, ze se automat ponecha nedeterministicky a hledani vzorku dat se provadi na nem, pricemz jeden stav je n-bitove cislo, kde n je pocet stavu onoho nedet. automatu. Je pak mozne jakoby byt ve vice stavech najednou - ve kterych to urcuji bity onoho n-bitoveho cisla. Prechodova funkce je snad zrejma ;-))))
