ساختمان ماشین‌ها
ساختمات ماشین‌ها یک تکنیک ریاضی مهم در نظریهٔ آتوماتا یا نظریه ماشین‌ها می‌باشد که برای نشان دادن وجود یک ماشین خودکار با یک ویژگی مطلوب تعیین شده، استفاده می‌شود. در بیشتر مواقع، آن به صورت یک الگوریتم ارائه می‌شود که یک ویژگی مطلوب را به عنوان ورودی می‌گیرد و یک ماشین خودکار با آن ویژگی را به عنوان خروجی تولید می‌کند. بسیاری از مسائل سخت در نظریه ماشین‌ها عبارت است از پیدا کردن ساختمان درست یک ماشین خودکار است به طوری که این مسئله در آن قابل حل باشد. برای مثال، ساختمان مشهور در نظریه McNaughton این سؤال را جواب داد که آیا ماشین بوخی غیر قطعی همیشه قابل تبدیل به یک ماشین مولر قطعی است.
مثال
[ویرایش]ساختمان مجموعهٔ توانی یک الگوریتم برای ساخت یک ماشین متناهی قطعی از یک ماشین متناهی غیر قطعی داده شده‌است.
بهینگی یک ساختمان
[ویرایش]یک ساختمان ماشین‌ها را بهینه می‌نامند اگر یک ورودی برای ساختمان وجود داشته باشد به گونه‌ای که هیچ ماشینی که ویژگی مطلوب را برآورده می‌سازد و پیچیدگی کمتری از خروجی ساختمان دارد، وجود نداشته باشد.
پیوند به بیرون
[ویرایش]- "Automata construction" (به انگلیسی).