[Libfsd-devel] Determinizacija-a-a-a!

[Ivan P. <va...@ne...>]

Snoshti napravih determinizacija na NFA (koeto e vsushtnost konstruktora na 
DFA ot NFA). Pichove, trjabva da vi kazha che otdavna ne sum pisal neshto 
deto da me nakara da mislja tolkova. Hem go znam algorituma do poslednija 
detail i vse pak na praktika mi se oteli vola dokato go napravja. Krajnija 
rezultat e baja izchisten, makar i da turpi kritiki otkum efektivnost. 

Oshte ne sum commitnal (beshe 2.30 i sled purvite njakolko determiniriani 
avtomata prosto pripadnah v legloto) no vi prashtam primer - "x(a*|b*)y" 
suotvetno NFA i DFA.

Osven tova neshto interesno e worst case-a na algorituma za determinizacija -- 
deto vodi do exponencialen vzriv na sustojanijata. Primera e napravo velik!
Reguljarnijat izraz ".*1[01]{12}" generira NFA s 29 sustojanija i DFA s 
8193! :) Intuitivno tozi izraz kazva "vsichki dumi, koito imat edinica 12 
pozicii predi kraja". I ponezhe avtomata ne mozhe da gleda napred, toj 
trjabva da pomni kakvo e stanalo predi 12 pozicii. I ponezhe na nego pametta 
sa mu sustojanijata, toj trjabva da ima put v grafa si za vseki vuzmozhen 
razvoj, demek vsichki vectori ot nuli e edinici s razmernost 12. Seshtate 
se.. Za shtastie takiva reguljarni izrazi mnogo rjadko se sreshtat i v 99% ot 
sluchaite vsichko e mnogo burzo i dovolno.