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