2022 AFJ Cvičenie č. 3 - Nedeterministické KA, determinizácia

Zhrnutie prednášky

Cvičenie z predmetu Automaty a formálne jazyky najprv vysvetľuje zmysel determinizácie nedeterministických konečných automatov (NKA). Výsledný deterministický automat (DKA) je ekvivalentný pôvodnému, teda akceptuje presne tie isté reťazce, no o akceptácii rozhodne lineárne vzhľadom na dĺžku vstupu, zatiaľ čo NKA musí prehľadávať všetky výpočtové vetvy s exponenciálnou zložitosťou v najhoršom prípade. Na reťazcoch AA a ABA je to ukázané porovnaním výpočtov v oboch automatoch. Následne sa rozoberá typická úloha z testu: pre NKA so štyrmi stavmi a epsilon prechodmi zistiť, ktoré reťazce akceptuje, pričom stačí nájsť jeden akceptačný výpočet. Postupne sa overujú reťazce ε, A a B.

• - NKA a jemu zodpovedajúci DKA sú ekvivalentné a akceptujú presne tie isté reťazce.
• - NKA sa ľahšie konštruujú, ale ťažšie sa používajú; DKA sa ľahšie simulujú a implementujú.
• - Zamietnutie reťazca v NKA vyžaduje vyčerpať všetky výpočtové vetvy, v DKA stačí jeden výpočet dĺžky vstupu.
• - Zložitosť výpočtu NKA je v najhoršom prípade exponenciálna, DKA má vždy lineárnu zložitosť.
• - Stavy v DKA sa označujú množinami stavov NKA, pričom prázdna množina je neakceptačný stav.
• - Reťazec je akceptovaný v NKA, ak existuje aspoň jeden akceptačný výpočet, ostatné vetvy nemusia byť akceptačné.
• - Epsilon prechody umožňujú akceptovať napríklad prázdny reťazec cez stav Q1 alebo reťazec A viacerými spôsobmi.

Zhrnutie pripravené s pomocou AI z prepisu videa.