Konstrukce automatů - Automata construction

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Konstrukce automatů"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Květen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie automatů, konstrukce automatů je důležitá matematická technika používaná k prokázání existence automatu s určitou požadovanou vlastností. Velmi často se prezentuje jako algoritmus který bere požadovanou vlastnost jako vstup a produkuje jako výstup automat s vlastností.

Mnoho tvrdých problémů v teorii automatů zahrnuje nalezení správné konstrukce automatu tak, aby bylo možné na problém odpovědět. Například slavná stavba v McNaughtonova věta odpověděl na otázku, pokud není deterministický Büchi automat lze vždy přeložit do a deterministický Mullerův automat.

Příklad

Konstrukce Powerset je algoritmus pro konstrukci a deterministický konečný automat od daného nedeterministický konečný automat.

Optimalita konstrukce

Konstrukce automatů se nazývá optimální pokud existuje vstup do konstrukce tak, že neexistuje žádný automat, který uspokojí požadovanou vlastnost s menší velikostí složitosti než výstup konstrukce.