ساختمان پاورست
From Wikipedia, the free encyclopedia
در نظریه محاسبات ونظریه اتوماتا، ساختمان پاورست یا زیر مجموعه ساختمان یکی از روشهای تبدیل کردن یک اتوماتون تعینناپذیر متناهی (NFA) به ماشینهای تعینپذیر حالات متناهی (DFA) میباشد که شبیه تشخیص زبان صوری میباشد. در این نظریه خیلی مهم است زیرا که براساس NFA بناشده است اگر چه انعطافپذیری زیادی دارد ولی قادر به شناسایی تمام زبانهایی که توسط DFA شناسایی میشود نیست. به بیان دیگر NFA انعطافپذیری زیادی دارد اما چون بعضی از زبانها را قادر به تبدیل به DFA نیستند را نمیتوان به صورت فرمولی درآورد بخاطر همین کاراییش کمتر از DFA هست حتماً باید تبدیل شود تا بتوان گفت فرمولی برایش وجود دارد.
این خیلی مهم است برای تمرین تبدیل کردن ساختار آسانتر NFA به DFA بسیار کارآمد انجام پذیرد در حالی که اگر، n ایستگاه دارد، نتیجه تبدیل به DFA میتواند 2n ایستگاه داشته باشد، یک عدد بزرگ نمایی که بعضی از اوقات ساختار غیر عملی برای NFAهای بزرگ میشود (نمیشود تبدیل کرد).
این ساختار، بعضی اوقات Rabin–Scott powerset construction یا زیر مجموعهٔ ساختار نامیده میشود. تا با این واسطهٔ متمایزی بین ساختارهای متشابه برای نوعهای دیگر از اتوماتون قائل شونند که اولین بار توسط مایکل رابین و دانا اسکات در ۱۹۹۵ بیان شد.