تبدیلِ NFA به DFA لزوماً ماشینِ کمینه نمی‌سازد. پس از داشتنِ DFA کامل، می‌توان حالت‌هایی را که هیچ ادامهٔ ورودی آن‌ها را از نظرِ پذیرش جدا نمی‌کند، در یک بلوک ادغام کرد. این تمرین، حالتِ غیرقابل‌دسترسی، پارتیشنِ پایدار و پسوندِ متمایزکننده را جدا کنترل می‌کند؛ صرفِ شبیه‌بودنِ نامِ حالت‌ها کافی نیست.
شش حالت، ولی فقط پنج حالتِ قابلِ دسترسی
ماشینِ اصیلِ ما حالت‌هایِ S، B، Z، W، F و U و الفبایِ a و b دارد. آغاز S و پذیرنده‌ها F و U هستند. S با a به Z و با b به B می‌رود؛ B با a به W و با b به B می‌رود. Z و W با a به F و با b به B می‌روند. F با a در F می‌ماند و با b به B می‌رود؛ U رویِ هر دو حرف در خود می‌ماند.
از S هرگز به U نمی‌رسیم؛ پس آن حالت، حتی با پذیرنده‌بودن، در زبانِ آغازِ ماشین سهمی ندارد. پیش از کمینه‌سازی کنار گذاشته می‌شود. پنج حالتِ دیگر قابلِ دسترسی‌اند و زبانِ این مثال، رشته‌هایی است که به aa پایان می‌یابند؛ این ادعا بعداً با رابطهٔ انتقال و آزمونِ مستقل کنترل می‌شود.
پذیرنده و ناپذیرنده در یک بلوک نمی‌مانند
پارتیشنِ نخستِ حالت‌هایِ قابلِ دسترسی، بلوکِ F و بلوکِ B، S، W، Z است. وضعیتِ پذیرشِ رشتهٔ خالی همین دو دسته را جدا می‌کند. در هر دور، امضایِ یک حالت، بلوکِ مقصدِ a و بلوکِ مقصدِ b است؛ حالت‌هایِ هم‌بلوک با امضایِ متفاوت شکسته می‌شوند.
پس از یک دور، سه بلوکِ {B، S}، {F} و {W، Z} داریم. دو باره امضاها را محاسبه می‌کنیم و پارتیشن عوض نمی‌شود. توقف به دلیلِ تمام‌شدنِ یک بودجهٔ دلخواه نیست؛ قاعدهٔ شکستن دیگر هیچ بلوکِ تازه‌ای نمی‌سازد.
| بلوکِ ماشینِ تازه | با a | با b | پذیرنده |
|---|---|---|---|
| {B، S} | {W، Z} | {B، S} | خیر |
| {W، Z} | {F} | {B، S} | خیر |
| {F} | {F} | {B، S} | بله |
از هر عضوِ بلوک، همان انتقال را بگیریم
برای ساختِ جدولِ quotient، یک نماینده از هر بلوک انتخاب می‌شود. کد کنترل می‌کند که برای همهٔ اعضایِ همان بلوک وهر حرف، بلوکِ مقصد یکسان باشد. اگر فقط نماینده را بررسی کنیم، ممکن است یک ادغامِ نادرست پنهان بماند و خروجی به انتخابِ نماینده وابسته شود.
این رابطهٔ انتقال همراه با حفظِ آغاز و پذیرندگی، دلیلِ حفظِ زبان برای تمامِ واژه‌هاست. در کنارِ آن، تمام ۵۱۱ رشتهٔ a و b با طولِ ۰ تا ۸ واقعاً در ماشینِ اصلی، ماشینِ سه‌حالته و عبارتِ مستقلِ endswith('aa') برابر کنترل می‌شوند. شمارشِ محدود به‌تنهایی اثباتِ همهٔ طول‌ها نیست.
چرا سه بلوکِ باقی‌مانده را باز هم ادغام نکنیم؟
از F در مقایسه با حالتِ ناپذیرنده، پسوندِ خالی کافی است تا پذیرش متفاوت شود. برای S یا B در مقایسه با Z یا W، پسوندِ a متمایزکننده است:یکی هنوز ناپذیرنده و دیگری پذیرنده می‌شود. پس جفت‌هایِ بلوک‌هایِ متفاوت، ادامهٔ جداکننده دارند.
مرجعِ مستقل، رویِ گرافِ زوجِ حالت‌ها BFS می‌زند و کوتاه‌ترینِ پسوندِ جداکننده را پیدا می‌کند. برای تمامِ ده جفتِ پنج حالتِ قابلِ دسترسی گواه ثبت می‌شود؛ اگر پسوندی وجود دارد، تمامِ طول‌هایِ کوچک‌تر هم کنترل می‌شوند. برای B و S یا W و Z هیچ پسوندِ جداکننده‌ای در گرافِ کاملِ زوج‌ها پیدا نمی‌شود.
دامنهٔ ماشین را روشن نگه داریم
شش ورودیِ نامعتبر، از انتقالِ ناقص و مقصدِ ناشناخته تا پذیرنده یا آغازِ ناشناخته، حرفِ تکراری و بیش از ۸ حالت رد می‌شوند. الفبا حداکثر ۳ حرفِ تک‌نویسه‌ای دارد؛ تابع برای هر حالت وهر حرف یک مقصدِ معلوم می‌خواهد. NFA، یالِ ε یا امکان‌هایِ موتورِ regex در این ورودی پشتیبانی نشده‌اند.
ساختِ زیرمجموعهٔ NFA ماشینِ قطعیِ معادل می‌سازد؛ اینجا حالت‌هایِ همان نوعِ ماشین را کمینه می‌کنیم. Aho–Corasick محلِ چند الگو را گزارش می‌کند، نه این زبانِ کلِ رشته. ادامه در مبانی هوش مصنوعی؛ پیاده‌سازیِ Hopcroft، مدلِ زبانی یا parser داخلیِ اپرا ادعا نشده است.
فایل تمرین و منبع
کد کاملِ تمرینِ مستقل و کنترل‌ها؛ Python · ورودی و تمامِ خروجیِ اجرای واقعی؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.