ماشین متناهی غیرقطعی تعمیم‌یافته

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

تعریف رسمی

GNFA می‌تواند به عنوان یک ۵ تایی، (S, Σ, T, s, a) تعریف شود که از موارد زیر تشکیل شده است:

• مجموعهٔ متناهی از وضعیت‌ها (S)
• مجموعه‌ای متناهی که الفبا نامیده می‌شود (Σ)
• تابع انتقال (T: (S ∖ {a}) × (S ∖ {s}) → R)
• وضعیت شروع (s ∈ S)
• وضعیت پذیرش (a ∈ S)

که R مجموعه‌ای از همهٔ اصطلاحات با قاعده تحت‌الفبای Σ است. تابع انتقال، یک جفت از دو وضعیت را به عنوان متغیر ورودی خود می‌گیرد و یک اصطلاح با قاعده را خارج می‌کند. این با بقیهٔ ماشین‌های حالت متناهی متفاوت است، که یک وضعیت را به عنوان ورودی و یک ورودی از الفبا می‌گیرد (یا یک رشتهٔ تهی در مورد ماشین‌های حالت متناهی غیر قطعی) و وضعیت بعدی را خارج می‌کند (یا مجموعه‌ای از وضعیت‌های ممکن در مورد ماشینهای حالت متنهاهی غیر قطعی). یک DFA یا NFA می‌تواند به سادگی به یک GNFA تغییر یابد و سپس GNFA می‌تواند به راحتی با انداختن مکرر قسمت‌های آن در یک یال مجموعهٔ S = {s, a}، به یک عبارت منظم تغییر یابد. به طور مشابه GNFAها می‌توانند به NFAها کاهش یابند که این کار توسط تغییر عملگرهای بیان با قاعده، به یال‌های جدید تا زمانی که هر یال با یک بیان با قاعده که متناظر با رشته‌ای به طول حداکثر ۱ است برچسب گذاری شود، انجام می‌شود. NFA به نوبه خود می‌تواند به DFAهایی با استفاده از ایجاد مجموعهٔ توانی کاهش یابد. این نشان می‌دهد GNFA مجموعهٔ مشابهی از زبان‌های صوری را مانند DFAها و NFAها شناسایی می‌کند.

منابع

https://en.wikipedia.org/wiki/Generalized_nondeterministic_finite_automaton