Názor k článku Regulární výrazy v příkladech od smrt - Jojo, to je, ale sestevit nedeterm. automat pro...

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 ;-))))