ساختمان پاورست

در نظریه محاسبات ونظریه اتوماتا،  ساختمان پاورست یا زیر مجموعه ساختمان یکی از روش‌های تبدیل کردن یک اتوماتون تعین‌ناپذیر متناهی (NFA) به ماشین‌های تعین‌پذیر حالات متناهی (DFA) می‌باشد که شبیه تشخیص زبان صوری می‌باشد. در این نظریه خیلی مهم است زیرا که براساس NFA بناشده است اگر چه انعطاف‌پذیری زیادی دارد ولی قادر به شناسایی تمام زبان‌هایی که توسط DFA شناسایی می‌شود نیست. به بیان دیگر NFA انعطاف‌پذیری زیادی دارد اما چون بعضی از زبان‌ها را قادر به تبدیل به DFA نیستند را نمی‌توان به صورت فرمولی درآورد بخاطر همین کاراییش کمتر از DFA هست حتماً باید تبدیل شود تا بتوان گفت فرمولی برایش وجود دارد.

این خیلی مهم است برای تمرین تبدیل کردن ساختار آسان‌تر NFA به DFA بسیار کارآمد انجام پذیرد در حالی که اگر، n ایستگاه دارد،  نتیجه تبدیل به DFA می‌تواند 2n ایستگاه داشته باشد، یک عدد بزرگ نمایی که بعضی از اوقات ساختار غیر عملی برای NFAهای بزرگ می‌شود (نمی‌شود تبدیل کرد).

این ساختار، بعضی اوقات Rabin–Scott powerset construction یا زیر مجموعهٔ ساختار نامیده می‌شود. تا با این واسطهٔ متمایزی بین ساختارهای متشابه برای نوع‌های دیگر از اتوماتون قائل شونند که اولین بار توسط مایکل رابین و دانا اسکات در ۱۹۹۵ بیان شد.

 ساختار 
ساختمان پاورست به‌طور مستقیم به NFA اعمال می‌شود بطوری‌که تغییرات حالت، بدون مصرف نمادهای ورودی (با نام " ε-moves ") اجازه نمی‌دهد. چنین ماشینی می‌تواند به عنوان
۵-عنصر 
در نظر گرفته شود
که در آن Q مجموعه‌ای از حالات تعریف شده است، Σ مجموعه‌ای از نمادهای ورودی، T تابع انتقال (که یک حالت و نماد ورودی را به یک مجموعه از حالت‌ها می‌نگارد،  حالت اولیه است و F مجموعه‌ای از حالات پذیرش است. DFA مربوطه، حالاتی که زیر مجموعه Q می‌باشد را داراست. حالت اولیه برای ماشین‌های تعین‌پذیر حالات متناهی،  می‌باشد که مجموعه‌ای تک عضوی از حالات اولیه است. تابع انتقال DFA حالت S را (به نمایندگی از یک زیر مجموعه از Q) وسمبل ورودی X را به مجموعه
{ T(S,x) = ∪{T(q,x) | q ∈ S
می‌نگارد، مجموعه‌ای از همه حالات که می‌تواند با گذارX از حالت در S تحقق یابد. حالتS از DFA حالت پذیرا است اگر و تنها اگر حداقل یک عضو S یک حالت پذیرا از NFAباشد.

 مثال 
NFA زیر دارای ۴ حالت است. حالت ۱ , حالت اولیه است و حالت ۳ و ۴ حالت پذیرفته شده است. الفبای آن شامل ۲ نماد ۰ و۱ است. و دارای ε-moves است. حالت ۱ , حالت اولیه است.
210px
حالت اولیه DFA ساخته شده از NFA مجموعه‌ای از تمام حالت‌هایی از NFA است که می‌توانند از حالت ۱ با ε حرکت قابل رسیدن است.
انتقال از {۱٬۲,۳} با نماد ورودی ۰ با پیکانی از حالت ۱ به حالت ۲ ادامه می‌دهد. و همچنین نه حالت ۲ و حالت ۴ خروجی ε-moves دارند. در نتیجه{T({1,2,3},0) = {۲٬۴ و و با همان استدلال DFA کامل ساخته شده از NFA در زیر نشان داده شده است.
300px

 جستارهای وابسته 
مایکل رابین

نظریه محاسبات

نظریه اتوماتا

ماشین‌های تعین‌پذیر حالات متناهی

اتوماتون تعین‌ناپذیر متناهی

 منابع 

 Michael Sipser, Introduction to the Theory of Computation . (See. Theorem 1.19, section 1.2, pg. 55.)
 John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. . (See chapter 2.)


 M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959

رده:ماشین متناهی
رده:نظریه اتوماتا
رده:نظریه محاسبات