Prijeđi na sadržaj

Aciklički deterministički konačni automat

Izvor: Wikipedija

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 s 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 | uredi kôd]
Nedovršeni članak Aciklički deterministički konačni automat koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.