الفبا، رشته و زبان
هر درس نظریهٔ زبان با سه پرسش ساده شروع می‌شود: نماد چیست، رشته چگونه ساخته می‌شود، و زبان چه چیزی است؟ پاسخ این سه پرسش، تمام فصل‌های بعدی را می‌سازد؛ چون گرامرها و ماشین‌ها چیزی جز ابزارِ تولید و تشخیص همین رشته‌ها نیستند.
الفبا چیست؟
الفبا مجموعه‌ای متناهی و ناتهی از نمادهاست که آن را با Σ نشان می‌دهیم. هر عضو الفبا یک «حرف» یا «نماد» است و هیچ ترتیبی هم روی آن‌ها لازم نیست.
رشته، دنباله‌ای متناهی از نمادها
رشته، دنباله‌ای متناهی از نمادهای الفباست. طول رشته را با |w| نشان می‌دهیم و رشتهٔ بدون هیچ نماد را رشتهٔ تهی می‌نامیم و با λ (یا ε) نمایش می‌دهیم.
توجه کنید که λ یک رشته است، نه «هیچ چیز»؛ به همین دلیل می‌تواند عضو یک زبان باشد.
زبان = مجموعه‌ای از رشته‌ها
زبان روی الفبای Σ، هر مجموعه‌ای از رشته‌های ساخته‌شده از حروف Σ است. پس زبان خودش یک «مجموعه» است و اعضایش «رشته» هستند:
Σ* و Σ+
Σ* مجموعهٔ همهٔ رشته‌های متناهی روی Σ است، از جمله رشتهٔ تهی. اگر تنها رشتهٔ تهی را کنار بگذاریم، Σ+ به دست می‌آید:
نمونهٔ الفبای یک‌حرفی
Σ = { a } ⟹ همهٔ رشته‌ها به شکل توانی از a هستند:
نمونهٔ الفبای دوحرفی
Σ = { a, b } ⟹ ترتیب حروف هم مهم است، پس ab ≠ ba:
چهار زبان نمونه از کلاس
در برگهٔ ۱۴ چهار زبان نوشته شد؛ هر کدام یک «الگو» را نشان می‌دهد که بعداً برایش گرامر یا ماشین می‌سازیم:
| زبان | تعریف | نمایش گسترده | ویژگی |
|---|---|---|---|
| L₁ | { ab, cd, ef } | — | متناهی؛ فقط سه رشته |
| L₂ | { ab, bb, ba, abbb, bbb } | — | متناهی، بدون الگوی شمارشی |
| L₃ | { anbn : n ≥ 0 } | { λ, ab, aabb, aaabbb, … } | نامتناهی؛ تعداد a و b برابر |
| L₄ | { a2nb2m+1 : n, m ≥ 0 } | { b, aab, bbb, aabbb, … } | نامتناهی؛ a زوج‌بار و b فرد‌بار |
یک نکتهٔ ظریف در برگه
گسترش نقل‌شده در یادداشت کلاس، {b, aa, a²b², …}، با تعریف این جدول هم‌خوان نیست. برای L₄ = {a2nb2m+1 : n,m≥0}، چند عضو درست عبارت‌اند از b، a²b و b³؛ اما aa و a²b² عضو آن نیستند. توانِ b باید فرد باشد.
کارت‌های مرور سریع
روی هر کارت کلیک کنید تا پاسخ را ببینید.
عملیات روی زبان‌ها
چون زبان یک مجموعه است، اول از همه می‌توانیم عملیات مجموعه‌ای انجام دهیم: اجتماع، اشتراک، تفاضل و مکمل. اما یک عملیات مخصوص زبان‌ها هم داریم که روی رشته‌ها بنا شده است: الحاق. از الحاق، توان و بستار ساخته می‌شود و همین‌ها زبان‌های نامتناهی را از زبان‌های کوچک می‌سازند.
الحاق دو زبان
الحاق دو زبان، مجموعهٔ همهٔ رشته‌هایی است که از چسباندن یک رشته از زبان اول به یک رشته از زبان دوم ساخته می‌شوند:
در دفتر کلاس، این عملیات با نماد × هم نوشته شده است: L₁ × L₂. ترتیب مهم است؛ L₁L₂ و L₂L₁ لزوماً یکی نیستند.
۲ رشته × ۴ رشته = ۸ رشته
| aa | bb | bc | ba | |
|---|---|---|---|---|
| a | aaa | abb | abc | aba |
| ba | baaa | babb | babc | baba |
حاصل الحاق، هشت رشته است:
توان، ستاره و پلاس
Lⁿ
توان صفر هر زبان، مجموعهٔ شامل رشتهٔ تهی است و هر توان بعدی، الحاق زبان با خودش:
L1 = L
L2 = L · L
Ln = L · Ln−1
L* و L+
ستارهٔ کلینی، اجتماع همهٔ توان‌ها از صفر است؛ پلاس از یک شروع می‌شود:
L* = L0 ∪ L1 ∪ L2 ∪ …
مکمل نسبت به Σ*
مکمل یک زبان، همهٔ رشته‌های روی الفبا که در آن زبان نیستند. دقت کنید مکمل همیشه نسبت به Σ* گرفته می‌شود، نه نسبت به زبان دیگر:
Lᴿ
معکوس زبان، مجموعهٔ معکوسِ همهٔ رشته‌های آن است. مثلاً اگر L = {anbn} باشد:
چهار اتحاد که باید حفظ باشند
- خنثی بودن λ در الحاق: برای هر رشتهٔ w داریم wλ = λw = w. به همین دلیل L·{λ} = L.
- معکوس الحاق جابه‌جا می‌شود: (L₁L₂)R = L₂R L₁R — اول معکوسِ تکهٔ دوم، بعد تکهٔ اول.
- معکوس و ستاره: (L*)R = (LR)*.
- معکوس اجتماع: (L₁ ∪ L₂)R = L₁R ∪ L₂R.
L⁰ = {λ} است، نه ∅
تهی‌بودنِ زبان با داشتنِ رشتهٔ تهی یکی نیست: ∅ ≠ {λ}. بنابراین L0 = {λ} برای هر زبانی، حتی L = ∅. در نتیجه ∅* = {λ} ولی ∅+ = ∅.
آزمایشگاه زبان
عملیات را انتخاب کنید تا نتیجه روی همان دو زبان کلاس، زنده ساخته شود.
گرامر و زبان گرامر
تا اینجا زبان را «مجموعه» دیدیم. حالا می‌خواهیم زبان را تولید کنیم: گرامر دستگاهی است که با چند قاعدهٔ جای‌گذاری، از یک نماد شروع به رشته‌های زبان می‌رسد.
گرامر، یک چهارتایی
- V — مجموعهٔ غیرپایانی‌ها (متغیرها)؛ همان نمادهایی که باید جای‌گذاری شوند.
- T — مجموعهٔ پایانی‌ها؛ حروفی که در رشتهٔ نهایی می‌مانند (V ∩ T = ∅).
- S — نماد شروع؛ ریشهٔ اشتقاق و عضوی از V.
- P — مجموعهٔ قواعد به شکل x → y با x ∈ (V ∪ T)* V (V ∪ T)* و y ∈ (V ∪ T)*.
قید مهم: سمت چپ باید دست‌کم یک غیرپایانی داشته باشد؛ سمت راست می‌تواند تهی باشد. بنابراین S → λ مجاز است، ولی جای‌گذاریِ صرفِ یک نماد پایانی مثل a → b قاعدهٔ این گرامر نیست.
⇒ و ⇒*
اگر با یک قاعده، بخشی از رشتهٔ فعلی را جای‌گذاری کنیم، می‌نویسیم u ⇒ v. اگر چند گام (شامل صفر گام) لازم باشد، u ⇒* v می‌نویسیم.
L(G)
زبانِ گرامر، مجموعهٔ همهٔ رشته‌های پایانی است که از S قابل اشتقاق‌اند:
ساخت {aⁿbⁿ}
هر بار که قاعدهٔ S → aSb اعمال شود، یک a به چپ و یک b به راست اضافه می‌شود؛ پس تعدادشان همیشه برابر می‌ماند. با S → λ اشتقاق تمام می‌شود:
- S ⇒ λ ⟹ λ
- S ⇒ aSb ⇒ aλb ⟹ ab
- S ⇒ aSb ⇒ aaSbb ⇒ aabb
- S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb
در نتیجه، زبان گرامر چنین است:
گرامر رشته‌های متعادل
این گرامر زبان رشته‌هایی را می‌سازد که تعداد a و b در آن‌ها برابر است. قاعدهٔ S → SS اجازهٔ کنار هم گذاشتن دو رشتهٔ متعادل را می‌دهد و دو قاعدهٔ دیگر، تعادل را حفظ می‌کنند.
برای نمونه، رشتهٔ a⁴b²a⁵b⁸a ده a و ده b دارد و با این گرامر قابل تولید است. طرحِ یک اشتقاق (با استفاده از کنارهم‌گذاری و جفت‌سازی) چنین است:
رشتهٔ b⁵a²b³a⁶ هم ۸ a و ۸ b دارد و این گرامر آن را می‌پذیرد؛ رد کردنش اشتباه است. پنج بار S → bSa بدهید و بخش میانیِ a²b³a = (aabb)(ba) را با S → SS بسازید. در این گرامر، برابریِ تعداد a و b هم لازم است و هم کافی؛ ترتیب دلخواه این دو حرف با قواعد پوشش داده می‌شود.
درخت اشتقاق چه می‌گوید؟
درخت اشتقاق، همان اشتقاق است ولی بدون ترتیب؛ هر گرهٔ داخلی یک غیرپایانی است و فرزندانش، سمت راست قاعده‌ای که اعمال شده. برگ‌ها (از چپ به راست) رشتهٔ نهایی را می‌سازند. اگر برگ‌های یک درخت را جابه‌جا کنیم، ممکن است رشتهٔ نامعتبر بسازیم — به همین دلیل ترتیب فرزندان مهم است.
گرامرنویسی: چهار تمرین کلاس
صورت مسئله همیشه یکی است: «زبان داده شده، گرامر بساز.» روش کار: الگوی شمارش را پیدا کن، برای هر «حافظه» یک غیرپایانی بگذار، و با قواعد، الگو را بازتولید کن.
زبان: { bn a bm : n, m ≥ 0 }
A → bA | λ
دو نسخهٔ A، قبل و بعد از a، هر تعداد b تولید می‌کنند. دو رخدادِ A مستقل از هم بازنویسی می‌شوند؛ به‌کاربردن یک نام برای هر دو، تعداد bهای دو طرف را برابر نمی‌کند. مثلاً S ⇒ AaA ⇒ baA ⇒ babb هم مجاز است.
ساده‌ترین راه، دو غیرپایانی برای «زوج» و «فرد» است:
E → a S | b E | λ
S یعنی «تا اینجا تعداد a زوج است» (حالت شروع و غیرقابل‌پایان) و E یعنی «فرد است» (با قاعدهٔ λ قابل‌پایان). هر a وضعیت را جابه‌جا می‌کند و b آن را تغییر نمی‌دهد. در دفتر هم ایدهٔ «اضافه‌کردن aها جفت‌جفت» آمده بود؛ همان ایده، اینجا به شکل دو حالت نوشته شده است.
قاعدهٔ aSb یک a و یک b اضافه می‌کند؛ Sb تنها b اضافه می‌کند و قاعدهٔ پایهٔ S → b وجودِ حداقل یک b اضافی را تضمین می‌کند. اگر قاعدهٔ پایه λ بود، زبانِ نادرستِ m≥n (شامل λ) تولید می‌شد.
همان گرامر مثال ۲؛ ساده‌ترین نمونهٔ زبان «غیرمنظم» که با گرامر ساخته می‌شود ولی با هیچ DFAای قابل تشخیص نیست (در فصل‌های بعد ثابت می‌شود).
ماشین متناهی معین (DFA)
گرامر زبان را تولید می‌کرد؛ ماشین آن را تشخیص می‌دهد. DFA ماشینی است که ورودی را حرف‌به‌حرف می‌خواند، در هر لحظه دقیقاً در یک حالت است، و در پایان یا پذیرش را اعلام می‌کند یا رد را. کلمهٔ «معین» یعنی برای هر حالت و هر حرف، دقیقاً یک مقصد وجود دارد.
پنج‌تایی ماشین
تابع انتقال توسعه‌یافته:
δ*(q, λ) = q و δ*(q, wa) = δ( δ*(q, w), a ). رشتهٔ w پذیرفته می‌شود اگر و تنها اگر δ*(q₀, w) ∈ F.
رشته‌های با طول زوج
دو حالت کافی است: «تا اینجا طول زوج است» و «طول فرد است». هر حرف، حالت را عوض می‌کند:
| حالت | a | b |
|---|---|---|
| → * q₀ | q₁ | q₁ |
| q₁ | q₀ | q₀ |
شمارش تعداد a به پیمانهٔ ۴
برای شرط «باقی‌ماندهٔ تعداد a بر ۴ صفر باشد»، به چهار حالت نیاز داریم: باقی‌ماندهٔ ۰، ۱، ۲ و ۳. هر a حالت را یک قدم جلو می‌برد و هر b حالت را نگه می‌دارد:
قاعدهٔ کلی: برای شمردنِ تعداد a به پیمانهٔ k، k حالت لازم است؛ برای دو شرط هم‌زمان (مثل زوج بودن a و زوج بودن b) حالت‌ها حاصل‌ضرب می‌شوند: 2 × 2 = 4.
شبیه‌ساز زنده
ماشین زیر رشته‌هایی را می‌پذیرد که تعداد a در آن‌ها بخش‌پذیر بر ۳ باشد. رشته‌ای بنویسید و مسیر اجرا را ببینید:
فقط حروف a و b خوانده می‌شوند.
| حالت | با a | با b | پایانی؟ |
|---|---|---|---|
| → q₀ | q₁ | q₀ | بله؛ باقی‌ماندهٔ صفر |
| q₁ | q₂ | q₁ | خیر |
| q₂ | q₀ | q₂ | خیر |
حالت مرده را فراموش نکنید
در DFA تابع δ باید برای هر حالت و هر حرف تعریف شده باشد. اگر در طراحی به حالتی رسیدید که ادامه دادن بی‌فایده است (مثلاً رشته دیگر قابل پذیرش نیست)، یک حالت مرده بگذارید که همهٔ حروف را به خودش برگرداند. نبودن حالت مرده یعنی ماشین ناقص است، نه هوشمندتر.
ماشین متناهی نامعین (NFA)
دانشجو اولین بار وقتی NFA را می‌بیند می‌پرسد: «مگر ماشین می‌تواند چند راه را هم‌زمان برود؟» پاسخ: در مدل بله؛ در پیاده‌سازی نه. NFA یک ابزار طراحی است: نوشتن‌اش آسان‌تر است و بعداً به DFA تبدیل می‌شود.
پنج‌تایی با تابع انتقال مجموعه‌ای
تفاوت اصلی با DFA در هم‌دامنه است: خروجی δ یک مجموعه از حالت‌ها است، نه یک حالت. پس برای یک حرف ممکن است صفر، یک یا چند مقصد وجود داشته باشد.
پذیرش در NFA: رشتهٔ w پذیرفته می‌شود اگر دست‌کم یک مسیر محاسباتی به حالت پایانی برسد:
چند مقصد برای یک حرف
در حالت q₂ با خواندن a هم می‌توان به q₄ رفت و هم به q₅؛ ماشین هر دو راه را «حدس می‌زند» و اگر یکی به پذیرش برسد، کافی است.
گذار λ (تهی)
NFA می‌تواند بدون مصرف نماد از حالتی به حالت دیگر بپرد. این کار مدل‌سازی «انتخاب آزاد» را ساده می‌کند؛ DFA گذار λ ندارد، اما می‌تواند همان زبان را پس از تبدیل بپذیرد.
سه حالت برای {aⁿ : n ≥ 1} ∪ {bᵐaᵏ : m,k ≥ 0}
از حالت شروع دو راه داریم: مستقیم با a به حالت پایانی (شاخهٔ aⁿ)، یا با λ به حالت میانی، خواندن هر تعداد b و بعد با یک λ دیگر به حالت پایانی:
چون m = k = 0 هم مجاز است، رشتهٔ تهی با مسیرِ دو گذار λ پذیرفته می‌شود. دقت: اجتماعِ عنوان در واقع همان b* a* است، چون {aⁿ:n≥1} ⊆ {bᵐaᵏ:m,k≥0}؛ شاخهٔ مستقیم a فقط یک مسیر جایگزینِ اضافی است، نه زبانی تازه.
بستار λ (λ-closure)
برای اجرای دقیق NFA، از هر حالت مجموعه‌ای از حالت‌ها را نگه می‌داریم. بستار λ یک حالت، همهٔ حالت‌هایی است که با صفر یا چند گذار λ از آن قابل دسترسی‌اند (خود حالت هم داخل مجموعه است). قاعدهٔ اجرا: اول بستار λ حالت فعلی را بگیر، بعد برای حرف بعدی δ را اعمال کن و باز بستار λ نتیجه را بگیر.
DFA یا NFA؟
| ویژگی | DFA | NFA |
|---|---|---|
| تابع انتقال | δ : Q × Σ → Q | δ : Q × (Σ ∪ {λ}) → 2Q |
| تعداد مقصد برای یک حرف | دقیقاً یکی | صفر، یکی یا چندتا |
| گذار بدون مصرف نماد | ندارد | دارد (λ) |
| مسیر محاسباتی | یکتا | ممکن است چندتا |
| سختی طراحی | بیشتر | کمتر (انعطاف بالا) |
| قدرت بیان | یکسان — هر NFA یک DFA هم‌ارز دارد | |
زبان منظم چیست و ماشین متناهی چه کاری نمی‌تواند بکند؟
زبانی منظم است اگر یک DFA (یا به‌طور معادل یک NFA) آن را بپذیرد. عبارت‌های منظم نیز دقیقاً همین خانواده را توصیف می‌کنند: برای نمونه (ab)* و b*a* منظم‌اند؛ اجتماع، الحاق و ستارهٔ زبان‌های منظم هم منظم می‌مانند.
اما {anbn:n≥0} منظم نیست: ماشین با تعداد حالت‌های ثابت نمی‌تواند تعداد نامحدود aها را نگه دارد و سپس همان تعداد b را تطبیق دهد. گرامر S→aSb|λ آن را تولید می‌کند، ولی هیچ DFA/NFAای آن را نمی‌پذیرد. بنابراین «برای هر گرامر، DFA بساز» درست نیست؛ تبدیلِ بخش بعد فقط برای NFA است.
هم‌ارزی NFA و DFA
هم‌ارزی در سطح زبان، نه ساختار
دو ماشین هم‌ارزند اگر زبان یکسانی را بپذیرند؛ حتی اگر حالت‌ها و یال‌هایشان کاملاً متفاوت باشد:
برای هر NFA یک DFA وجود دارد
اگر L زبان پذیرفته‌شده توسط NFAی MN = (QN, Σ, δN, q₀, FN) باشد، آنگاه DFAیی مانند MD = (QD, Σ, δD, S₀, FD) وجود دارد که L = L(MD).
ایدهٔ اثبات: کافی است روشی سازنده بدهیم. حالت‌های DFA، مجموعه‌هایی از حالت‌های NFA هستند؛ چون تعداد زیرمجموعه‌های یک مجموعهٔ متناهی، متناهی است، ماشین حاصل هم متناهی است.
الگوریتم ساخت زیرمجموعه‌ای، گام‌به‌گام
- شروع: حالت آغازین DFA را S₀ = closureλ({q₀}) بگیرید. اگر گذار λ نداریم، همان {q₀} است.
- یال‌گذاری: برای هر مجموعه‌حالت S و هر حرف a∈Σ، ابتدا مقصدها را اجتماع بگیرید و سپس بستار λ را حساب کنید: δD(S,a) = closureλ(⋃q∈S δN(q,a)).
- حالت جدید: اگر مجموعهٔ حاصل قبلاً در GD نبود، آن را به‌عنوان یک حالت تازه اضافه کنید (و صف کار را ادامه دهید).
- پایانی‌ها: هر مجموعه‌حالت که دست‌کم یک حالت پایانیِ NFA را در خود دارد، در DFA پایانی است.
- تکمیل: اگر برای یک حرف مجموعهٔ مقصد تهی شد، ∅ را حالت مرده بگذارید و گذارهای آن را به خودش برگردانید تا DFA کامل شود.
سه حالت NFA ← هفت حالت DFA
NFA زیر را در نظر بگیرید (الفبای {0,1}، حالت پایانی q₁):
| δN | 0 | 1 |
|---|---|---|
| → q₀ | {q₀,q₁} | {q₁} |
| * q₁ | {q₂} | {q₂} |
| q₂ | ∅ | {q₂} |
حالا همان گام‌ها را اجرا می‌کنیم. حالت شروع {q₀} است؛ با 0 به {q₀,q₁} و با 1 به {q₁} می‌رویم و همین‌طور ادامه می‌دهیم:
| حالت DFA | 0 | 1 | پایانی؟ |
|---|---|---|---|
| → {q₀} = A | {q₀,q₁} = B | {q₁} = C | خیر |
| {q₀,q₁} = B | {q₀,q₁,q₂} = D | {q₁,q₂} = E | بله |
| {q₁} = C | {q₂} = F | {q₂} = F | بله |
| {q₀,q₁,q₂} = D | {q₀,q₁,q₂} = D | {q₁,q₂} = E | بله |
| {q₁,q₂} = E | {q₂} = F | {q₂} = F | بله |
| {q₂} = F | ∅ = G | {q₂} = F | خیر |
| ∅ = G (مرده) | G | G | خیر |
نتیجه: هفت حالت. حالت G = ∅ همان حالت مرده است؛ در تخته کلاس آن را q₃ نامیده بودند. حالت‌های پایانی DFA دقیقاً آن‌هایی هستند که q₁ را در خود دارند: B, C, D, E.
ایدهٔ اثبات در یک خط
با استقرا روی طول رشته ثابت می‌شود که حالتِ DFA پس از خواندن w، دقیقاً برابر مجموعهٔ همهٔ حالت‌هایی است که NFA می‌تواند پس از خواندن w در آن‌ها باشد. پس شرطِ پذیرش در DFA دقیقاً معادلِ ناتهی بودن اشتراک مجموعهٔ حالت‌های NFA با F است و زبان یکی می‌شود.
کمینه‌سازی DFA
دو ماشین می‌توانند زبان یکسانی را بپذیرند ولی یکی ۲۰ حالت داشته باشد و دیگری ۴ حالت. کمینه‌سازی یعنی پیدا کردن کوچک‌ترین DFA هم‌ارز. چرا مهم است؟ چون هر حالت یعنی حافظه، و هر یال یعنی منطق؛ ماشین کوچک‌تر هم ارزان‌تر است هم قابل‌فهم‌تر.
دو حالت چه وقت یکی می‌شوند؟
دو حالت qi و qj ادغام‌پذیرند اگر برای هر رشتهٔ ممکن، هر دو یا هر دو پذیرفته شوند یا هر دو رد شوند:
و ادغام‌ناپذیرند (قابل تمیز) اگر دست‌کم یک رشته پیدا شود که یکی را بپذیرد و دیگری را رد کند:
چهار گام تا جدول کامل
- پاک‌سازی: حالت‌های غیرقابل دسترس را حذف کنید — حالت‌هایی که از q₀ هیچ مسیری به آن‌ها نیست. (برگهٔ ۲۰: در یک ماشین چهارحالته، q₁ هیچ یال ورودی نداشت و حذف شد.)
- علامت اولیه: هر جفت (پایانی، غیرپایانی) را ادغام‌ناپذیر علامت بزنید؛ چون رشتهٔ λ آن‌ها را از هم جدا می‌کند.
- انتشار: اگر δ(p,a) = pa و δ(q,a) = qa و جفت (pa, qa) قبلاً علامت خورده، جفت (p,q) را هم علامت بزنید.
- تکرار: گام ۳ را تا وقتی هیچ جفت تازه‌ای علامت نمی‌خورد تکرار کنید؛ جفت‌های بی‌علامتِ باقی‌مانده، هم‌ارزند و کلاس‌های ادغام را می‌سازند.
تعداد جفت‌های نامرتب برای n حالت: n(n−1)/2 — همان تعداد خانه‌های جدول مثلثی.
پنج حالت ← چهار حالت
ماشین زیر را با حالت‌های q₀ … q₄ و حالت‌های پایانی {q₂, q₄} در نظر بگیرید:
| حالت | 0 | 1 |
|---|---|---|
| → q₀ | q₁ | q₃ |
| q₁ | q₂ | q₄ |
| * q₂ | q₁ | q₄ |
| q₃ | q₂ | q₄ |
| * q₄ | q₄ | q₄ |
جدول علامت‌گذاری:
| q₀ | q₁ | q₂ | q₃ | q₄ | |
|---|---|---|---|---|---|
| q₀ | ✗ | ✗ | ✗ | ✗ | |
| q₁ | ✗ | ✓ | ✗ | ||
| q₂ | ✗ | ✗ | |||
| q₃ | ✗ | ||||
| q₄ |
چرا q₁ و q₃ ادغام‌پذیرند؟ هر دو غیرپایانی‌اند، با 0 به q₂ و با 1 به q₄ می‌روند؛ یعنی رفتار آیندهٔ آن‌ها دقیقاً یکسان است.
پنج حالت ← دو حالت
در این ماشین سه حالت q₁, q₂, q₃ پایانی‌اند. برای آنکه ادغام فقط به شکل وابسته نباشد، جدولِ انتقالِ نمونهٔ زیر را هم بررسی کنید؛ همهٔ پنج حالت از q₀ قابل دسترس‌اند:
| حالت | 0 | 1 |
|---|---|---|
| → q₀ | q₁ | q₂ |
| * q₁ | q₂ | q₄ |
| * q₂ | q₃ | q₀ |
| * q₃ | q₁ | q₄ |
| q₄ | q₃ | q₁ |
در هر دو حالتِ غیرپایانی، هر ورودی به یک حالت پایانی می‌رسد؛ در سه حالت پایانی، 0 داخل کلاس پایانی می‌ماند و 1 به کلاس غیرپایانی می‌رود. پس دو کلاس هم‌ارزی داریم:
| q₀ | q₁ | q₂ | q₃ | q₄ | |
|---|---|---|---|---|---|
| q₀ | ✗ | ✗ | ✗ | ✓ | |
| q₁ | ✓ | ✓ | ✗ | ||
| q₂ | ✓ | ✗ | |||
| q₃ | ✗ | ||||
| q₄ |
از کلاس‌ها به ماشین جدید
- هر کلاس هم‌ارزی، یک حالت از M̂ می‌شود.
- اگر δ(qi, a) = qj در ماشین اولیه باشد، از کلاس qi با حرف a به کلاس qj یال می‌کشیم.
- کلاسی که q₀ را در خود دارد، حالت شروع است.
- کلاسی که دست‌کم یک حالت پایانی دارد، حالت پایانی است.
- فقط حالت‌های غیرقابل‌دسترس را حذف کنید؛ نداشتن یال ورودی به‌تنهایی دلیل حذف نیست (حالت شروع ممکن است یال ورودی نداشته باشد).
نتیجهٔ تئوریک: ماشین حاصل کمینه است و هر دو حالت آن، قابل تمیزدادن‌اند.
بانک تمرین و پاسخ
تمرین‌های کتاب در دو فصل تقسیم می‌شوند: فصل ۲ (زبان‌ها و گرامرها، تمرین ۱ تا ۲۳) و فصل ۳ (کاربردها، تمرین ۱ تا ۹). در این بخش، تمرین‌های کلیدی با پاسخ کوتاه آمده‌اند؛ بقیه برای تمرین شخصی در کتاب موجودند.
جمع‌کنندهٔ دودویی: دو حالت، یک بیت نقلی
جمع دو عدد دودویی (بیت‌به‌بیت، از کم‌ارزش‌ترین بیت) فقط به یک چیز نیاز دارد: «آیا از جمع قبلی نقلی داشتیم؟» پس دو حالت کافی است: بدون نقلی و با نقلی.
| حالت | (0,0) | (0,1) یا (1,0) | (1,1) |
|---|---|---|---|
| بدون نقلی | خروجی 0 → بدون نقلی | خروجی 1 → بدون نقلی | خروجی 0 → با نقلی |
| با نقلی | خروجی 1 → بدون نقلی | خروجی 0 → با نقلی | خروجی 1 → با نقلی |
این مثال نشان می‌دهد نظریهٔ زبان فقط «ریاضیات انتزاعی» نیست؛ همان منطقی که یک DFA دوحالته توصیف می‌کند، داخل یک مدار جمع‌کننده هم هست.
دستهٔ ۱ · عملیات و خواص زبان‌ها
استقرا روی n: پایه n=0 که |λ|=0؛ گام: |un+1| = |unu| = |un| + |u| = n|u| + |u|.
تعریف بازگشتی: aR=a و (wa)R = a wR. اثبات با استقرا روی طول v؛ برای v=λ بدیهی و برای v=wa داریم (uwa)R = a(uw)R = a wR uR = (wa)RuR.
استقرا روی طول w؛ گام: (wa)R = a wR پس ((wa)R)R = (a wR)R = (wR)R a = wa.
روش: رشته را از چپ به راست به بلوک‌های ab / aa / baa بشکنید. هر رشته‌ای که دقیقاً به ۴ بلوک تقسیم شود، در L⁴ هم هست. مثلاً ab·ab·aa·baa = ababaabaa و ab·aa·aa·baa = abaaaabaa هر دو در L⁴ (و طبعاً در L*) هستند؛ رشته‌هایی که باقی‌مانده یا بلوک نامعتبر دارند، بیرون می‌مانند.
همهٔ رشته‌ها جز aa و bb؛ یعنی L̄ = {λ, a, b, ab, ba} ∪ {w : |w| ≥ 3}. توجه کنید که λ هم در مکمل است، چون در L نیست.
چون L ∪ L̄ = Σ* و Σ* نامتناهی است. اگر هر دو متناهی بودند، اجتماعشان متناهی می‌شد؛ تناقض.
خیر. فرض کنیم L* = L̄* = S. چون L ∪ L̄ = Σ* و هر دو زیرمجموعهٔ S هستند، نتیجه می‌شود S = Σ*. حالا حرف a ∈ Σ را در نظر بگیرید: برای اینکه a ∈ L̄* باشد و طولش یک است، باید خودش عضو L̄ باشد (الحاق دو رشتهٔ ناتهی طول ≥ ۲ می‌دهد). همین استدلال برای همهٔ حروف نشان می‌دهد Σ ⊆ L̄، پس هیچ حرفی در L نیست و رشته‌های تک‌حرفی در L* نیستند؛ اما L* = Σ* بود. تناقض.
عضویت دوطرفه: هر w ∈ (L₁L₂)R به شکل (xy)R = yRxR با x∈L₁, y∈L₂ است، پس در L₂RL₁R است؛ عکس آن هم مشابه.
هر عضو (L*)* الحاق چند رشته از L* است و هر رشتهٔ L* خودش الحاق چند رشته از L است؛ پس کل عبارت الحاق چند رشته از L است و در L* قرار دارد. عکس آن بدیهی است (L* ⊆ (L*)*).
دستهٔ ۲ · گرامرها
حداقل یک a: S → A a A , A → aA | bA | λ
حداکثر سه a: S → A | A a A | A a A a A | A a A a A a A , A → bA | λ
حداقل سه a: S → A a A a A a A , A → aA | bA | λ
در هر مورد A نقش «هر تعداد b (و در حالت‌های حداقلی، a اضافی)» را دارد.
هر دور، یک ab تولید می‌کند و در پایان λ می‌گیرد: L = (ab)*. گرامر جایگزین ساده: S → abS | λ.
این گرامر هیچ قاعدهٔ خاتمه‌ای ندارد: A و B همیشه باقی می‌مانند؛ پس L(G)=∅. برای ساخت طول‌های فرد، گرامر درستِ نمونه S → a | aaS است و {a,aaa,aaaaa,…} را می‌سازد.
L₂: S → aSb | λ
L₃: S → aA , A → aAb | λ
L₄: S → aSb | aaa
برای L₁L₂ و L₁∪L₂ و ستاره‌ها، می‌توان از گرامرهای ترکیبی استفاده کرد؛ مثلاً L₁L₂ با دو نماد شروع مجزا و قاعدهٔ S → S₁S₂ ساخته می‌شود (به شرط جدا بودن غیرپایانی‌ها).
مرکز رشته، دو حرف یکسان است؛ سپس هر دو طرف قرینه اضافه می‌شود.
این گرامر رشته‌هایی را می‌سازد که با حذف جفت‌های متقارن a…b یا b…a به یک a تنها می‌رسند؛ به‌عبارت دیگر ساختار تودرتویی دارند که در مرکز آن یک a است و تعداد a یکی بیشتر از b است. مثال‌ها: a, aab, baa, aaabb, abaab. «aba» در این گرامر تولید نمی‌شود، هرچند تعداد a آن یکی بیشتر است.
ابتدا E → aEbE | bEaE | λ را برای همهٔ رشته‌های با تعداد برابر a و b بسازید. برای اختلافِ دقیقاً یک: S → EaE؛ برای اختلافِ مثبتِ دلخواه: P → EaE | EaP. بلوک‌های E تعادل دارند و هر a میان آن‌ها اختلاف را یک واحد زیاد می‌کند.
برای اجازه‌دادنِ c در هر جای رشته، گرامرِ تعادل را این‌طور گسترش دهید: E → aEbE | bEaE | cE | λ. سپس برای اختلاف دقیقاً یک S → EaE و برای اختلاف مثبت P → EaE | EaP را به کار ببرید؛ c هیچ اثری بر اختلاف a و b ندارد.
S→aSb|ab|λ و S→aAb|ab , A→aAb|λ هم‌ارز نیستند: اولی λ را هم می‌سازد و زبانش {anbn: n≥0} است؛ دومی تنها n≥1 را می‌سازد. اگر S→λ را به دومی اضافه کنیم، هم‌ارز می‌شوند. اما S→aSb|bSa|SS|a با S→aSb|bSa|a هم‌ارز نیستند: اولی با SS رشته‌های بیشتری (مثل aa) می‌سازد.
دستهٔ ۳ · ماشین‌ها
دو حالت؛ هر حرف حالت را عوض می‌کند و حالت شروع، پایانی است (طول صفر زوج است).
چهار حالت به‌صورت زوج (زوج/فرد a، زوج/فرد b)؛ فقط حالتی که a فرد و b زوج است پایانی است. تعداد حالت‌ها = حاصل‌ضرب دو شمارنده = ۲×۲.
همان ماشین مثال ۶: q₀ با λ به q₁ (حلقهٔ b)، q₁ با λ به q₂ (پایانی، حلقهٔ a)، و کمان مستقیم a از q₀ به q₂.
سه حالت: q₀ (شروع و پایانی) --a--> q₁ --b--> q₂؛ از q₂ با λ به q₀ برگردید تا بلوک ab تمام شود؛ یا با c به q₀ برگردید تا بلوک abc کامل شود. q₀ شروع و پایانی است، پس λ هم در ستاره پذیرفته می‌شود.
مثال ۷ بخش ۶: هفت حالت شامل حالت مرده؛ حالت‌های پایانی هر مجموعه‌ای که q₁ را دارد.
جدول جفت‌ها را بسازید، جفت‌های پایانی/غیرپایانی را علامت بزنید، انتشار دهید و کلاس‌ها را ادغام کنید. دو مثال کامل در بخش ۷ حل شده است.
جمع‌بندی، جدول نمادها و آزمون
جدول نمادها
| نماد | معنی | یادآوری |
|---|---|---|
| Σ | الفبا | مجموعهٔ متناهی و ناتهی از نمادها |
| Σ* | بستار ستاره‌ای الفبا | همهٔ رشته‌ها، شامل λ |
| λ | رشتهٔ تهی | |λ| = 0 |
| L* / L+ | بستار زبان | L* = L+ ∪ {λ} |
| L̄ | مکمل زبان | Σ* − L |
| Lᴿ | معکوس زبان | (L₁L₂)ᴿ = L₂ᴿL₁ᴿ |
| G=(V,T,S,P) | گرامر | V غیرپایانی، T پایانی |
| δ | تابع انتقال | DFA: به Q؛ NFA: به 2Q |
| F | حالت‌های پایانی | در DFA: δ*(q₀,w) ∈ F |
| M̂ | ماشین کاهش‌یافته | حاصل کمینه‌سازی |
شش اشتباه رایج
۱. L⁰ = ∅
نه! L⁰ = {λ}. تهی‌بودن زبان با داشتن رشتهٔ تهی فرق دارد.
۲. δ ناقص
در DFA برای هر حالت و هر حرف باید یک مقصد داشته باشیم؛ حالت مرده را جا نیندازید.
۳. پذیرش در NFA
کافی است یک مسیر به پایانی برسد: δ*(q₀,w) ∩ F ≠ ∅، نه اینکه همهٔ مسیرها برسند.
۴. حالت پایانی در تبدیل
هر مجموعه‌حالت که دست‌کم یک حالت پایانی NFA را دارد، پایانی است.
۵. فراموش‌کردن حذف حالت غیرقابل دسترس
قبل از علامت‌گذاری، حالت‌هایی که از q₀ مسیر ندارند را حذف کنید.
۶. λ در DFA
DFA گذار λ ندارد؛ اگر جایی λ دیدید، ماشین NFA است (یا باید تبدیل شود).
آزمون کوتاه
پاسخ درست را انتخاب کنید؛ بازخورد فوری می‌گیرید.
پاسخ: C {aa, aab, aba, abab} — L² = {aa, aab, aba, abab}؛ هر عضو L با هر عضو L الحاق می‌شود.
پاسخ: B {λ} — توان صفر هر زبان، مجموعهٔ شامل رشتهٔ تهی است.
پاسخ: A {aⁿbⁿ : n ≥ 0} — هر بار یک a به چپ و یک b به راست اضافه می‌شود، پس تعدادشان برابر می‌ماند.
پاسخ: C ۳ — برای شمردن به پیمانهٔ ۳، سه حالت (باقی‌ماندهٔ ۰، ۱، ۲) لازم است.
پاسخ: B تابع انتقال آن به 2 Q می‌رود و λ هم مجاز است — در NFA خروجی δ مجموعه‌ای از حالت‌هاست (2^Q) و ممکن است چند مقصد یا λ داشته باشد.
پاسخ: D مجموعه‌ای از حالت‌های NFA — حالت‌های DFA در ساخت زیرمجموعه‌ای، مجموعه‌هایی از حالت‌های NFA هستند و کلاس‌های هم‌ارزی در کمینه‌سازی، حالت‌های ماشین جدید را می‌سازند.
نقشهٔ منابع
هر بخش از کدام برگه‌های دست‌نویس یا صفحه‌های کتاب ساخته شده است:
| بخش | منبع | موضوع |
|---|---|---|
| ۱ | برگهٔ ۱۴ | زبان، الفبا، Σ* و Σ+ |
| ۲ | برگهٔ ۱۵ | الحاق، توان، ستاره، مکمل، معکوس |
| ۳ | برگه‌های ۱۶–۱۸ | گرامر، اشتقاق، گرامرنویسی |
| ۴ | برگهٔ ۱۹ + تختهٔ ۱۰–۱۱ | DFA و طراحی ماشین |
| ۵ | برگهٔ ۲۰ + تختهٔ ۸–۱۱ | NFA، گذار λ |
| ۶ | تختهٔ ۱۲–۱۶ | قضیهٔ هم‌ارزی و ساخت زیرمجموعه‌ای |
| ۷ | برگه‌های ۱۷–۲۸ | کمینه‌سازی و دو مثال کامل |
| ۸ | صفحه‌های ۳۳–۴۲ کتاب | تمرین‌های فصل ۲ و ۳ |
قبل از آزمون، این هفت مورد را بتوانید بی‌مکث بگویید
- تفاوت زبان، رشته و الفبا در یک جمله.
- تفاوت L* و L+ و جای λ.
- ساخت گرامر برای {aⁿbⁿ} و {aⁿbᵐ : m>n}.
- طراحی DFA برای «تعداد a بخش‌پذیر بر k».
- تفاوت هم‌دامنهٔ δ در DFA و NFA.
- چهار گام ساخت زیرمجموعه‌ای.
- سه گام روال علامت‌گذاری در کمینه‌سازی.