Deterministički konačni automat: razlika između inačica

DKAi su jedni od najpraktičnijih modela izračunljivosti, s obzirom da postoji trivijalan ''online'' algoritam koji ih simulira u linearnom vremenu i konstantnom prostoru nad tokom ulaznih simbola. Za dva dana DKAa postoje učinkoviti algoritmi za pronalaženje DKA koji prepoznaje uniju, presjek te komplement jezika koje oni prepoznaju. Također postoje učinkoviti algoritmi za određivanje da li DKA prihvaća bilo koji niz znakova, da li DKA prihvaća sve nizove znakova, da li dva DKA prihvaćaju isti jezik, te za pronalaženje DKA sa minimalnim brojem stanja za zadani jezik.

 

 

U drugu ruku, DKAi su strogo ograničene moći nad jezicima koje mogu prepoznati — mnogi jednostavni jezici, uključujući bilo koji problem čije rješenje zahtijeva više nego konstantan prostor, ne mogu biti prepoznati od strane DKA. Kanonski primjer jezika kojeg nijedan DKA ne može prepoznati jest jezik koji se sastoji od nizova znakova oblika ''aⁿbⁿ'' — konačan broj znakova a nakon kojeg slijedi jednaki broj znakova b. Može se pokazati da nijedan DKA ne može imati dovoljan broj stanja da prepozna takav jezik.

 

{{Formalni jezici i gramatike}}

[[Kategorija:Teorija automata]]

[[Kategorija:Računski modeli]]

[[de:Deterministischer endlicher Automat]]

[[en:Deterministic finite state machine]]

[[he:אוטומט סופי דטרמיניסטי]]

[[hu:Determinisztikus véges állapotú gép]]

[[ja:決定性有限オートマトン]]

[[pl:Deterministyczny automat skończony]]