Aciklički deterministički konačni automat

Izvor: Wikipedija
Skoči na: orijentacija, traži

Aciklički deterministički konačni automati (ADKA) su deterministički konačni automati bez ciklusa. Drugim riječima, mogu prihvaćati samo konačne jezike. Mogu biti korišteni kao podatkovna struktura za pohranu riječi sa iznimno brzim performansama pretraživanja. Minimizirani ADKA također mogu biti jako kompaktni. Veličina minimiziranog ADKA ne ovisi izravno o broju pohranjenih ključeva. Ustvari, nakon određene točke, što se više riječi pohranjuje u minimizirani ADKA, njegova se veličina počinje smanjivati. Pokazalo bi se da je njegova veličina ustvari povezana sa složenošću skupa nizova znakova (riječi). Podatkovna strukture trie je tipa ADKA.

Vidjeti također[uredi VE | uredi]


Computer-aj aj ashton 01.svg Nedovršeni članak Aciklički deterministički konačni automat koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.