برای تبدیل NFA به DFA، هر حالتِ ماشینِ تازه نمایندهٔ یک مجموعه از حالت‌های ماشینِ اولیه است. در حضورِ یالِ ε، باید حالت‌های قابل‌دسترسی بدون مصرفِ نویسه را هم حساب کنیم. این صفحه یک NFA پنج‌حالتهٔ ساختگی را واقعاً به جدولِ DFA تبدیل می‌کند، حالتِ مرده را نگه می‌دارد و رفتارِ دو ماشین را روی همهٔ۶۳رشتهٔ کوتاهِ انتخاب‌شده با تعریفِ مستقلِ زبان مقایسه می‌کند.
ماشینِ اولیه چه زبانی می‌خواند؟
الفبا فقط a و b است. از حالت۰ با ε به۱ و۳ می‌رویم. حالت۱ روی a در خودش می‌ماند و با b به۲ می‌رود؛ حالت۳ روی b در خودش می‌ماند و با a به۴ می‌رود. حالت‌های۲و۴ پذیرنده‌اند و خروجیِ نمادی ندارند. بنابراین یک شاخه هر تعداد a و در پایان دقیقاً یک b، و شاخهٔ دیگر هر تعداد b و در پایان دقیقاً یک a می‌خواند؛ صفر تکرار هم مجاز است.
به زبان نمادین، a*b یا b*a را داریم. a و b هر دو پذیرفته می‌شوند؛ aab و bba نیز پذیرفته‌اند. اما رشتهٔ خالی، aa، bb و aba پذیرفته نیستند. این عبارت‌ها فقط توصیفِ زبانِ همین ماشین‌اند؛ موتور regexِ آماده‌ای در تمرین اجرا نشده است.
بستارِ ε خودِ مجموعه را هم دارد
بستارِ εِ یک مجموعه، خودِ حالت‌ها و همهٔ حالت‌هایی است که با صفر یا چند حرکتِ ε از آن‌ها می‌رسیم. برای شروع، E({۰})={۰،۱،۳} است؛ این یک حالتِ DFA می‌شود، نه سه انتخابِ تصادفی. برای {۱} نیز بستار همان {۱} است، حتی اگر هیچ حرکتِ ε از آن نداشته باشیم.
کد با مجموعهٔ seen و صفِ کاری، بستار را تا نبودِ عضوِ تازه ادامه می‌دهد. این عملیات نویسه‌ای از ورودی مصرف نمی‌کند. حذفِ خودِ حالتِ آغاز از بستار به این دلیل که «حرکتِ ε انجام نشد»، قرارداد را خراب می‌کند.
برای کنترلِ توقف، همان تابعِ بستار را در نمونهٔ جدا با چرخهٔ εِ ۰→۱→۰ و رفت‌وبرگشتِ ۱و۲ اجرا کرده‌ایم؛ از {۰} دقیقاً {۰،۱،۲} برمی‌گردد و از مجموعهٔ خالی، خالی می‌ماند. مجموعهٔ seen جلوی بازدیدِ بی‌پایان را می‌گیرد. این آزمونِ جدا، NFA اصلی و هشت حالتِ DFA آن را تغییر نمی‌دهد.
یک انتقال، اجتماع و سپس بستار
برای مجموعهٔ S و نویسهٔ c، ابتدا از تک‌تک اعضای S همهٔ مقصدهایِ یالِ c را جمع می‌کنیم و سپس بستارِ εِ اجتماع را می‌گیریم. نتیجه یک مجموعهٔ تازه و یک حالتِ DFA است. از شروعِ {۰،۱،۳} با a به {۱،۴} و با b به {۲،۳} می‌رسیم.
مجموعهٔ {۱،۴} پذیرنده است، چون۴ پذیرندهٔ NFA است؛ لازم نیست همهٔ اعضای مجموعه پذیرنده باشند. از همین حالت با a به {۱} می‌رویم که پذیرنده نیست؛ پذیرفته‌بودنِ یک پیشوند، پذیرفته‌بودنِ همهٔ ادامه‌ها را تضمین نمی‌کند. مجموعه‌ها با ترتیبِ اعضا هویتِ تازه پیدا نمی‌کنند؛ {۱،۴} و {۴،۱} یک حالت‌اند.
فقط مجموعه‌هایِ قابل‌دسترسی را بسازیم
شروع را در صف می‌گذاریم؛ برای هر حالتِ برداشته‌شده و هر دو نویسه، انتقال را می‌سازیم. اگر مجموعهٔ مقصد تازه باشد، شناسه می‌گیرد و به صف می‌رود. در پایانِ این مثال، هشت مجموعهٔ قابل‌دسترسی داریم، نه اینکه همهٔ۳۲زیرمجموعهٔ ممکنِ پنج حالت را بی‌دلیل تولید کنیم.
| مجموعهٔ NFA | با a | با b | پذیرنده؟ |
|---|---|---|---|
| {۰،۱،۳} | {۱،۴} | {۲،۳} | خیر |
| {۱،۴} | {۱} | {۲} | بله |
| {۲،۳} | {۴} | {۳} | بله |
| مجموعهٔ خالی | خالی | خالی | خیر |
جدولِ کاملِ هشت حالت با شناسه، مجموعه، پذیرندگی و هر دو انتقال در JSON است. مجموعهٔ خالی حالتِ مرده است؛ انتقالِ گم‌شده را به پذیرش یا بازگشتِ خودکار به شروع تبدیل نمی‌کنیم. این حالت برای هر دو نویسه در خودش می‌ماند.
سه نتیجه را برای هر رشته برابر کنیم
شبیه‌سازِ NFA مجموعهٔ حالت‌های فعال را در هر نویسه جلو می‌برد. شبیه‌سازِ DFA فقط شناسهٔ فعلی را از جدول می‌خواند. تابعِ سوم، بدون استفاده از ماشین‌ها، بررسی می‌کند رشته با یکی از دو تعریفِ «تکرارِ یک حرف و سپس یک حرفِ مخالف» جور باشد. همهٔ رشته‌های a و b با طولِ صفر تا۵، یعنی۱+۲+۴+۸+۱۶+۳۲=۶۳حالت، واقعاً در هر سه سنجیده شده‌اند.
این بررسیِ کراندار به‌تنهایی اثباتِ هم‌ارزی برای همهٔ طول‌ها نیست. استدلالِ ساخت این است که حالتِ DFA پس از هر پیشوند دقیقاً مجموعهٔ حالت‌های فعالِ NFA را نمایندگی کند؛ قاعدهٔ اجتماع و بستار همین رابطه را حفظ می‌کند و پذیرندگی با وجودِ یک عضوِ پذیرنده تعیین می‌شود. فایل ادعای کمینه‌بودنِ DFA یا تبدیلِ تمامِ قابلیت‌های regexهایِ نرم‌افزاری را ندارد.
چرا این مثال مدلِ زبانی نیست؟
پذیرش در این ماشین به قراردادِ دقیقِ الفبا و انتقال وابسته است؛ معنیِ متن، احتمالِ واژه یا یادگیری از نمونه انجام نمی‌شود. نویسهٔ بیرون از a و b در اجرای منفی واقعاً رد می‌شود. KMP جای رخدادِ یک الگو را در متن می‌خواهد؛ مسئلهٔ اینجا پذیرشِ کلِ رشته و ساختِ ماشینِ معادل است.
برای کاربردِ چت و پاسخ‌گویی، سؤالِ واقعی، دادهٔ معتبر و اقدامِ مجاز را در چتِ سایتِ اپرا مشخص کنید. این آموزش وجودِ موتور NFA یا regexِ خاصی در محصول را وعده نمی‌دهد.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.