گرامر مستقل از متن و ماشین پشته‌ای: از پرانتزهای متوازن تا فرم نرمال چامسکی

یک گرامر، یک زبان

گرامر پرانتزهای متوازن فقط سه قاعده دارد: یک رشتهٔ متوازن یا خالی است، یا یک رشتهٔ متوازن داخل یک جفت پرانتز، یا دو رشتهٔ متوازن پشت سر هم.

این گرامر ساده است ولی برای الگوریتم‌ها مناسب نیست: قاعدهٔ اپسیلون دارد و سمت راست قاعده‌ها طول‌های مختلف دارد. فرم نرمال چامسکی شکل یکنواختی می‌دهد که هم اثبات‌ها را ساده می‌کند و هم الگوریتم CYK رویش کار می‌کند.

تبدیل به فرم نرمال چامسکی در پنج قدم

در فرم نرمال چامسکی هر قاعده یکی از این دو شکل است: یک متغیر به دو متغیر می‌رود (A → BC)، یا یک متغیر به یک پایانه (A → a). تنها استثنا S₀ → ε برای متغیر شروع است، اگر رشتهٔ خالی در زبان باشد.

قدم ۱: متغیر شروع تازه

S در سمت راست قاعده‌ها آمده است. یک متغیر شروع تازه S₀ → S اضافه کن تا متغیر شروع هیچ‌وقت در سمت راست نیاید. این کار بعداً اجازه می‌دهد فقط S₀ به اپسیلون برود.

قدم ۲: حذف قاعده‌های اپسیلون

S می‌تواند به اپسیلون برود. پس هر جا S در سمت راست آمده، نسخه‌ای بدون آن را هم اضافه کن. از S → SS قاعدهٔ S → S به دست می‌آید که بی‌اثر است و حذفش می‌کنیم. از S → (S) قاعدهٔ S → () به دست می‌آید. از S₀ → S هم S₀ → ε. حالا S به اپسیلون نمی‌رود:

قدم ۳: حذف قاعده‌های واحد

S₀ → S یک قاعدهٔ واحد است. به‌جایش همهٔ قاعده‌های S را برای S₀ هم بنویس:

قدم ۴: جدا کردن پایانه‌ها

در قاعده‌هایی که طولشان بیشتر از یک است، پایانه‌ها را با متغیر عوض کن: L → ( و R → ). حالا S → (S) می‌شود S → L S R و S → () می‌شود S → L R.

قدم ۵: دوتایی کردن

S → L S R سه متغیر در سمت راست دارد. متغیر تازهٔ Y → S R را بساز و بنویس S → L Y. نتیجهٔ نهایی:

این گرامر را با الگوریتم CYK روی همهٔ ۳۲٬۷۶۷ رشتهٔ پرانتزی تا طول ۱۴ امتحان کردیم و دقیقاً همان ۶۲۶ رشتهٔ متوازن را پذیرفت. ترتیب قدم‌ها مهم است: اگر قاعده‌های واحد را قبل از اپسیلون حذف کنی، حذف اپسیلون دوباره قاعدهٔ واحد می‌سازد.

دو نتیجهٔ فرم نرمال که در تست می‌آید

• طول اشتقاق: در فرم نرمال چامسکی هر رشتهٔ به طول n ≥ 1 دقیقاً با 2n − 1 قدم مشتق می‌شود؛ n − 1 قدم دوتایی که درخت را می‌سازند و n قدم که برگ‌ها را به پایانه تبدیل می‌کنند. مثلاً رشتهٔ ()() با ۷ قدم.
• الگوریتم CYK: جدولی می‌سازد که برای هر زیررشته می‌گوید کدام متغیرها آن را تولید می‌کنند، از زیررشته‌های کوتاه به بلند. زمانش O(n³) ضرب در اندازهٔ گرامر است.

ابهام: یک رشته، چند درخت

گرامری مبهم است که دست‌کم یک رشته با دو درخت تجزیهٔ متفاوت داشته باشد. مثال کلاسیک گرامر عبارت‌هاست:

رشتهٔ a+a*a دو درخت دارد: یکی که اول جمع را انجام می‌دهد و یکی که اول ضرب را. هرچه عملگرها بیشتر شوند، تعداد درخت‌ها سریع رشد می‌کند: با چهار عملوند ۵ درخت و با پنج عملوند ۱۴ درخت؛ همان عددهای کاتالان. راه رفعش لایه‌بندی اولویت‌هاست:

دو نکتهٔ تستی: ابهام ویژگی گرامر است نه زبان؛ یک زبان می‌تواند هم گرامر مبهم داشته باشد هم نامبهم. ولی زبان‌هایی هم هستند که هر گرامرشان مبهم است؛ به آن‌ها ذاتاً مبهم می‌گویند. تصمیم‌گیری دربارهٔ مبهم بودن یک گرامر دلخواه هم تصمیم‌ناپذیر است.

ماشین پشته‌ای

ماشین پشته‌ای یک ماشین متناهی است که یک پشته هم دارد. برای aⁿbⁿ، به ازای هر a یک نماد روی پشته می‌گذارد و به ازای هر b یکی برمی‌دارد؛ اگر پشته درست وقتی رشته تمام شد خالی شد، می‌پذیرد. ماشین پشته‌ای غیرقطعی دقیقاً همان قدرت گرامرهای مستقل از متن را دارد.

اینجا برخلاف ماشین‌های متناهی، غیرقطعی بودن قدرت بیشتری می‌دهد. زبان wwᴿ، یعنی رشته به‌علاوهٔ برعکسش، ماشین پشته‌ای غیرقطعی دارد: ماشین حدس می‌زند وسط رشته کجاست. ولی هیچ ماشین پشته‌ای قطعی آن را نمی‌پذیرد. اگر وسط را با یک نماد مثل c علامت بزنی، یعنی wcwᴿ، یک ماشین قطعی کافی است.

خواص بستاری: جایی که بیشتر اشتباه‌ها رخ می‌دهد

مثال برای اشتراک: aⁿbⁿc* و a*bⁿcⁿ هر دو مستقل از متن‌اند، ولی اشتراکشان aⁿbⁿcⁿ است که مستقل از متن نیست. از اینجا نبودن بستار زیر مکمل هم نتیجه می‌شود، چون اشتراک را می‌شود با اجتماع و مکمل ساخت. سطر آخر جدول ابزار مهمی است: برای اثبات مستقل از متن نبودن یک زبان، گاهی اشتراکش با یک زبان منظم ساده‌تر است.

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

چرا فرم نرمال چامسکی مهم است؟

چون شکل یکنواخت قاعده‌ها اثبات‌ها و الگوریتم‌ها را ساده می‌کند. الگوریتم CYK فقط روی این فرم کار می‌کند، درخت تجزیه دودویی می‌شود و طول هر اشتقاق دقیقاً 2n − 1 است. لم تزریق زبان‌های مستقل از متن هم با همین درخت‌های دودویی اثبات می‌شود.

ماشین پشته‌ای قطعی و غیرقطعی قدرت یکسانی دارند؟

نه. برخلاف ماشین‌های متناهی، ماشین پشته‌ای غیرقطعی قوی‌تر است. wwᴿ با ماشین غیرقطعی پذیرفته می‌شود ولی با هیچ ماشین قطعی نه. زبان‌های پذیرفته‌شده با ماشین پشته‌ای قطعی زیر مکمل بسته‌اند.

آیا اشتراک دو زبان مستقل از متن مستقل از متن است؟

لزوماً نه. aⁿbⁿc* و a*bⁿcⁿ هر دو مستقل از متن‌اند ولی اشتراکشان aⁿbⁿcⁿ نیست. اشتراک یک زبان مستقل از متن با یک زبان منظم اما همیشه مستقل از متن است.

در تبدیل به فرم نرمال، ترتیب قدم‌ها مهم است؟

بله. اول متغیر شروع تازه، بعد حذف اپسیلون، بعد حذف قاعده‌های واحد، بعد جدا کردن پایانه‌ها و آخر دوتایی کردن. حذف اپسیلون می‌تواند قاعدهٔ واحد تازه بسازد، مثل S → S از S → SS، پس باید قبل از حذف قاعده‌های واحد انجام شود.

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

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

قدم بعدی تو

گرامر S → aSb | ε را خودت به فرم نرمال چامسکی ببر، بعد این سه سؤال را جواب بده: ۱) رشتهٔ aabb با چند قدم مشتق می‌شود؟ ۲) زبان aⁿbⁿ ∩ a*b* مستقل از متن است؟ ۳) گرامر S → SS | a مبهم است؟

جواب‌ها: ۱) ۷ قدم، یعنی 2 × 4 − 1. ۲) بله؛ اشتراک با یک زبان منظم است و در واقع همان aⁿbⁿ است. ۳) بله؛ رشتهٔ aaa دو درخت دارد، (aa)a و a(aa).