زبان منظم، DFA و NFA برای کنکور: یک زبان، سه ساخت

سه ابزار، یک قدرت

یک زبان مجموعه‌ای از رشته‌هاست؛ اینجا رشته‌هایی از ۰ و ۱. سه ابزار برای توصیفش داریم:

• DFA (ماشین متناهی قطعی): از هر حالت با هر نماد دقیقاً به یک حالت می‌رود. رشته را نماد به نماد می‌خواند و اگر آخر کار در حالت پذیرش باشد، رشته را می‌پذیرد.
• NFA (ماشین متناهی غیرقطعی): از یک حالت با یک نماد می‌تواند به چند حالت برود، یا به هیچ حالتی. رشته پذیرفته می‌شود اگر دست‌کم یک مسیر به حالت پذیرش برسد.
• عبارت منظم: با اجتماع، الحاق و ستاره زبان را می‌نویسد؛ مثل (0+1)*1.

قضیهٔ اصلی این بخش این است که هر سه دقیقاً یک دسته زبان را توصیف می‌کنند. غیرقطعی بودن قدرت بیشتری نمی‌دهد؛ فقط ممکن است ماشین را خیلی کوچک‌تر کند.

مثال ۱: عددهای بخش‌پذیر بر ۳

زبان رشته‌های دودویی که مقدارشان بر ۳ بخش‌پذیر است. ترفند این است که لازم نیست کل عدد را به خاطر بسپاری؛ باقی‌ماندهٔ تقسیم بر ۳ کافی است. اگر تا اینجا باقی‌مانده r بوده و نماد b را بخوانی، عدد جدید 2r + b است. پس سه حالت داریم، باقی‌ماندهٔ ۰، ۱ و ۲، و حالت ۰ هم شروع است و هم پذیرش.

این ماشین را روی همهٔ رشته‌ها تا طول ۱۴ امتحان کردیم و با مقدار واقعی عددها یکی بود. سه حالت کمترین تعداد ممکن هم هست. همین ایده برای بخش‌پذیری بر هر عدد k کار می‌کند و DFAیی با k حالت می‌دهد.

مثال ۲: یک زبان، سه ساخت

زبان رشته‌هایی که سومین نماد از آخرشان ۱ است. این مثال نشان می‌دهد چرا NFA گاهی خیلی راحت‌تر است.

عبارت منظم

هر چیزی، بعد یک ۱، بعد دقیقاً دو نماد دلخواه:

NFA چهار حالته

حالت شروع روی هر نمادی در خودش می‌ماند. با خواندن یک ۱ می‌تواند «حدس بزند» که این همان ۱ سوم از آخر است و به حالت بعدی برود. از آنجا دو نماد دلخواه می‌خواند و به حالت پذیرش می‌رسد. اگر حدسش غلط بوده باشد، آن مسیر می‌میرد؛ کافی است یک مسیر درست وجود داشته باشد.

DFA هشت حالته

DFA نمی‌تواند حدس بزند. باید سه نماد آخر را همیشه به خاطر داشته باشد، چون هر کدام ممکن است بعداً سومین نماد از آخر شود. سه نماد آخر ۸ حالت ممکن دارند و هیچ دوتایشان را نمی‌شود یکی کرد. ساخت زیرمجموعه‌ای هم روی همان NFA دقیقاً ۸ حالت قابل‌دسترس می‌سازد.

این همان مثال کلاسیکی است که نشان می‌دهد انفجار 2ⁿ در تبدیل NFA به DFA واقعاً اتفاق می‌افتد و فقط یک کران بدبینانه نیست.

ساخت زیرمجموعه‌ای در یک نگاه

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

در تست معمولاً لازم نیست همهٔ 2ⁿ زیرمجموعه را بنویسی؛ فقط از زیرمجموعهٔ شروع جلو برو و زیرمجموعه‌های قابل‌دسترس را بساز.

دو اشتباه رایج

اشتباه ۱: «شمردن لازم دارد، پس نامنظم است»

زبان رشته‌هایی که تعداد زیررشته‌های 01 و 10 در آن‌ها برابر است را در نظر بگیر. به نظر می‌رسد باید دو شمارنده نگه داری، پس نامنظم است. ولی این دو تعداد هیچ‌وقت بیشتر از یکی با هم فاصله ندارند، چون 01 و 10 یکی در میان پیش می‌آیند. نتیجه: این دو تعداد برابرند دقیقاً وقتی که نماد اول و نماد آخر رشته یکی باشند، یا رشته خالی باشد. این زبان منظم است و کوچک‌ترین DFA آن ۵ حالت دارد.

در مقابل، زبان رشته‌هایی که تعداد ۰ و ۱ در آن‌ها برابر است واقعاً نامنظم است: ماشین باید اختلاف تعداد ۰ و ۱ را به خاطر بسپارد و این اختلاف می‌تواند هر عددی باشد، پس هیچ تعداد متناهی حالت کافی نیست.

اشتباه ۲: زیرمجموعهٔ زبان منظم لزوماً منظم نیست

(0+1)* منظم است و همهٔ رشته‌ها را دارد، پس هر زبانی زیرمجموعهٔ آن است؛ از جمله زبان‌های نامنظم مثل 0ⁿ1ⁿ. منظم بودن زیر اجتماع، اشتراک، مکمل، الحاق و ستاره حفظ می‌شود، ولی زیر «زیرمجموعه گرفتن» نه.

پرسش‌های پرتکرار

NFA از DFA قوی‌تر است؟

نه. هر NFA با ساخت زیرمجموعه‌ای به یک DFA معادل تبدیل می‌شود، پس هر دو دقیقاً زبان‌های منظم را می‌پذیرند. فرقشان در اندازه است: DFA معادل ممکن است تا 2ⁿ حالت داشته باشد.

چطور ثابت کنم زبانی منظم نیست؟

دو راه رایج داری. لم تزریق: اگر زبان منظم باشد، هر رشتهٔ به‌اندازهٔ کافی بلند را می‌شود طوری شکست که تکرار یک تکهٔ نزدیک ابتدا رشته را داخل زبان نگه دارد؛ برای نامنظم بودن، رشته‌ای پیدا کن که این کار برایش ممکن نیست. راه دوم مایهیل–نرود است: بی‌نهایت پیشوند پیدا کن که هر دوتایشان را پسوندی از هم جدا کند، مثل 0ⁱ برای زبان 0ⁿ1ⁿ.

کوچک‌ترین DFA را چطور پیدا کنم؟

حالت‌های غیرقابل‌دسترس را حذف کن و حالت‌های هم‌ارز را یکی کن. دو حالت هم‌ارزند اگر برای هر رشته‌ای که از آن‌ها ادامه بدهی، هر دو با هم بپذیرند یا با هم رد کنند. روش جدول: اول جفت‌های «پذیرش و غیرپذیرش» را جدا علامت بزن، بعد هر جفتی که با یک نماد به جفت علامت‌خورده می‌رود را علامت بزن، تا وقتی چیزی عوض نشود.

DFA برای اشتراک دو زبان چطور ساخته می‌شود؟

با ساخت ضربی: هر حالت جفتی از یک حالت هر ماشین است و هر دو ماشین هم‌زمان جلو می‌روند. مثلاً «تعداد ۰ زوج» دو حالت دارد و «تعداد ۱ فرد» هم دو حالت؛ اشتراکشان DFAیی با ۴ حالت می‌دهد که کوچک‌تر هم نمی‌شود.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم و نظریهٔ زبان‌ها و ماشین‌ها را، از زبان‌های منظم تا ماشین تورینگ، در کلاس نظریه درس می‌دهم؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. نتیجهٔ شاگردهایی که نظریه را کامل زدند در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

بدون نگاه به متن جواب بده: ۱) کوچک‌ترین DFA برای عددهای دودویی بخش‌پذیر بر ۳ چند حالت دارد؟ ۲) کوچک‌ترین DFA برای «چهارمین نماد از آخر ۱ است» چند حالت دارد؟ ۳) زبان رشته‌هایی که تعداد 01 و 10 در آن‌ها برابر است منظم است؟

جواب‌ها: ۱) ۳ حالت. ۲) ۱۶ حالت، یعنی 2⁴. ۳) بله؛ همان رشته‌هایی است که نماد اول و آخرشان یکی است، به‌علاوهٔ رشتهٔ خالی.