نرمالسازی گرامرها جلسه دوم

1396/1/12 احمدآبادی 3361

سلام حالتون چطوره ؟ خوب هستید؟ منم خوبم . امروز میخوام مبحث نرمال سازی را اگه عمری باشه براتون تمومش کنم . در مورد تمرین جلسه گذشته که بهتون دادم باید عرض کنم به محض این که من این تمرین را براتون قرار دادم سیلی از پیام های تهی برای من اومد که هنوز نتونستم همشو چک کنم. (حرف آخر : از روز اول ما باهم قرار گذاشتیم باهم بریم جلو . هنوز کسی به من پیامی درمورد جواب تمرین نداده پس من هم تا موقعی که شما جوابی به من ندهید تمرین را براتون حل نمیکنم. لطفا شجاعت به خرج دهید و اون تمرین را حل کنید هرچند اشتباه حل کنید . همین اشتباه حل کردنتون برای من ارزش داره . ) دیگه این بحثو بزاریم کنار و بریم سراغ ادامه مبحثمون.

  1. حذف بازکشتی از چپ:

هر قاعده یک گرامر مستقل از متن میتواند به یکی از دو شکل زیر باشد:

A →α1|α2|…..|αn

A →Aβ1|Aβ2|….|Aβn

 

شکل فوق بیان میکند که دنباله های سمت راست یک متغیر در یک گرامر مستقل از متن یا با همان متغیر شروع میشود ویا نه. اگر در یک گرامر مستقل از متن برای متغیری مانند A حداقا یک قاعده تولید به شکلی که با A شروع شود  داشته باشیم ، میگوییم قواعد A دارای بازگشتی از چپ است.

 

پس از یافتن ، برای متغیری که دارای بازگشتی از چپ است با تعریف یک متغیر کمکی برای آن متغیر و با استفاده از فرم زیر بازگشتی از چپ را حذف میکنیم.

A →αi|αiAˊ      1<=i<=n

Aˊ →βj|βjAˊ      1<=j<=m

 

مثال) بازگشتی از چپ را در گرامر زیر حذف کنید.

 

S →aSb|aAB

A→aA|Aba|aAb

B →Bab|BBa|bb

 

متغیر شروع هیچ قاعده ای ندارد که با خود متغیر شروع ، شروع شود پس این متغیر بازگشتی از چپ ندارد و عینا همین خط باید در گرامر نهایی نوشته شود.

 

متغیر A دارای بازگشتی از چپ می باشد . ( منظور من قاعده دوم این متغیر هست)  حالا برای حذف این بازگشتی ما باید به این ترتیب بریم جلو . اولا مابقی قواعد A که بازگشتی از چپ ندارند را پیدا کرده و ان هارا به عنوان α خواهیم شناخت . یعنی در این گرامر بغیر از قاعده دوم متغیر A ، قاعده اول و سوم این متغیر چون بازگشتی از چپ ندارند بالای سر اون ها یک نماد α قرار میدهیم.  حالا اون قاعده ای که بازگشتی از چپ دارد را پیدا کرده و از بعد از سمبل اول قاعده ( یعنی خود متغیر ) انرا با β علامت گذاری میکنیم. حالا طبق دستورالعمل  و فرمول گفته شده در بالا روند حذف بازگشتی از چپ را در پیش میگیریم.

یعنی خط دوم گرامر من تبدیل خواهد شد به:

A →aA|aAAˊ|aAb|aAbAˊ

Aˊ →ba|baAˊ

 

حالا همین کارو برای متغیر B انجام میدهیم. قاعده اول و دوم این متغیر بازگشتی از چپ دارند پس این دو قاعده را از بعد از اولین سمبل قاعده( که خود متغیر می باشد) علامت زده  وبالای این علامت β مینویسیم. اخرین قاعده متغیر B هم چون بازگشتی از چپ ندارد به عنوان α خواهیم شناخت.

 

 پس گرامر نهایی من خواهد شد:

S →aSb|aAB

A →aA|aAAˊ|aAb|aAbAˊ

Aˊ →ba|baAˊ

B →bb|bbBˊ

Bˊ →ab|abBˊ|Ba|BaBˊ

 

( خارج از کلاس)

 

 تا همین مقدار بازگشتی از چپ برای دوستانی که در دانشگاه این درس را گرفتن کافیه . حالا میخوام انواع بازگشتی از چپ را بهتون بگم که مربوط میشه به درس کامپایلر. ( چندنفر از دوستان درخواست کرده بودن درمورد انواع بازگشتی از چپ هم صحبت کنم. ) اولا در بازگشتی از چپ بالا که توضیح دادم ما دیگه قرار نیست λ هم داشته باشیم . برای همین در درس کامپایلر فرمول بازگشتی از چپ کمی متفاوته چون داشتن λ ایرادی نداره. اما روش حذف همون هست که گفته بودم. یعنی برای حذف بازگشتی از چپ باید یک متغیر کمکی تعریف کنیم و همون قضیه α وβ را روی آن ها پیاده کنیم.

در درس کامپایلر حذف بازگشتی از چپ را این گونه بیان میکنند:

برای حذف بازگشتی از چپ در یک گرامر ، پس از تعیین α ها و βها برای متغیری که بازگشتی از چپ دارد آن را باتوجه به مدل زیر تبدیل میکنیم.

A →αiAˊ    1<=i<=n

Aˊ →βjAˊ| λ   1<=j<=m

 

انواع بازگشتی ازچپ:

 

  1. بازگشتی از چپ مستقیم: یعنی متغیر ها به طورمستقیم (بدون واسطه) بازگشتی از چپ داشته باشند که برای حذف آن از الگوی گفته شده رفتار میکنیم.

مثال)

S →AB


B →abb|Ba|BBb

 

قاعده اول متغیر A و قاعده دوم و سوم متغیر B هرکدام بازگشتی ازچپ هستند و به صورت مستقیم هم بازگشتی از چپ دارند پس مثل الگوی  گفته شده بازگشتی از چپ را حذف میکنیم.

 

S →AB

A →abAˊ|bBAˊ

    ˊ →aAˊ| λ

B →abbBˊ

    ˊ →aBˊ|BbBˊ|λ

 

  1. بازگشتی از چپ غیر مستقیم: گاهی اوقات ممکن است متغیری مانند A دارای هیچ سمت راستی که با خود A شروع شود نباشد .اما ممکن است متغیر A با متغیری مانند B شروع شود که خود متغیر B حداقل یک بار با A شروع شده باشد در این صورت میگوییم A به طورغیر مستقیم دارای بازگشتی از چپ است.

 

   برای حذف بازگشتی از چپ غیرمستقیم باید ابتدا آن را به مستقیم تبدیل و سپس حذف کنیم . برای تبدیل بازگشتی از چپ غیر مستقیم به مستقیم ، به طور مثال اگر A با متغیر B شروع شده کافی است تمامی سمت راست های B را به A جایگزین کنیم.

مثال)

S →AB

A→Ba|aa|bB

B→Ab|bb

 

این گرامر بازگشتی از چپ مستقیم ندارد اما قاعده اول متغیر A با B شروع میشود که خود متغیر B هم در یکی از قواعدش با A شروع میشود پس بازگشتی از چپ غیر مستقیم خواهیم داشت. حالا من باید این گرامر را به بازگشتی مستقیم تبدیل کنم . برای اینکار  قاعده اول متغیر A را باید اصلاح کنم یعنی این قاعده:

 

A →Ba

برای اصلاح این قاعده باید تمامی سمت راست های متغیر B را در این قاعده جایگذاری کنم .

B→Ab|bb

پس این قاعده متغیر A خواهد شد :

A →Aba|bba

ودرنهایت کل قواعد تولید متغیر A به این صورت خواهد شد:

A →Aba|bba|aa|bB

 پس گرامر دارای بازگشتی از چپ مستقیم من خواهد بود:

 

حالا باید این گرامر را طبق حذف بازگشتی از چپ مستقیم بازنویسی اش کنم.

 

پس گرامر من خواهد شد :

S →AB

A →bbaAˊ|aaAˊ|bBAˊ

Aˊ →baAˊ|λ

B →Ab|bb

 

  1. بازگشتی از چپ پنهان: اگر چنانچه برای متغیری مانند A حداقل یک قاعده به فرم  A →Baα داشته باشیم و متغیر B دارای قاعده ای به فرم  B →λ باشد آنگاه میگوییم متغیر A دارای بازگشتی از چپ پنهان است. برای حذف این نوع بازگشتی از چپ ، ابتدا با جایگذاری تمامی سمت راست های B به جای متغیر B بازگشتی از چپ پنهان A را به بازگشتی از چپ مستقیم تبدیل میکنیم و سپس مانند روش های قبل آن را حذف میکنیم.

 

مثال)

S →AB

A →bbaAˊ|aaAˊ|bBAˊ

Aˊ →baAˊ|λ

B →Ab|bb

در این گرامر در اولین قاعده متغیر A من اگر به جای B از λ استفاده کنم میتوانم بگویم که متغیر A با خودش شروع شده است پس بازگشتی از چپ پنهان خواهیم داشت خب من باید این گرامر تبدیل کنم به بازگشتی از چپ مستقیم  . طبق روش گفته شده عمل خواهیم کرد که  متغیر A قاعده هایش به این ترتیب خواهد شد:

A →Ab|aAb|aa

و در نهایت گرامر ما خواهد شد:

S →aAB

A →Ab|aAb|aa

B →a|λ

 

الان این گرامر بازگشتی از چپ مستقیم دارد پس باید مثل قبل این بازگشتی را برطرف کنیم  . خب باید برای متغیر A مقادیر α و β را تعیین کنیم و مثل فرمول گفته شده گرامررابازنویسی کنیم . پس گرامر نهایی من خواهد شد:

 

S →aAB

A →aAbAˊ|aaAˊ

Aˊ →bAˊ|λ

B→a|λ

 

( پایان خارج از کلاس)

 

اول جلسه گذشته من براتون دو فرم نرمال چامسکی و گریباخ را نام بردم اما فقط در حد نام بردن بود وحالا میخوام براتون تعریفشون کنم.

فرم نرمال چامسکی:

یک گرامر به فرم نرمال چامسکی خواهد بود اگر و تنها اگر هرقاعده آن به یکی از دوشکل زیر باشد.

A →BC        A,B,C ԑ V,   a ԑ ∑

A →a

 

اگر بخواهم فرمول بالا را به زبان ساده برایتان بگویم اینطور باید بگم که : اگر گرامری بخواهد به فرم نرمال چامسکی باشد درهر قاعده آن یاباید دو متغیر داشته باشیم و یا یک الفبا.

 

 برای تبدیل یک گرامر مستقل از متن  به فرم نرمال چامسکی لازم است ابتدا  قوانین λ و قوانین زنجیر و متغیرهای بدون استفاده  حذف شوند.

مثال) گرامر زیر را به فرم نرمال چامسکی بنویسید.

S →aSb|aA

A →aA|a

 

 خوش بختانه این گرامر λ ندارد، زنجیر ندارد و متغیر غیرمفید هم ندارد. پس حالا میریم سراغ مرحله آخر .برای اینکه بخوام من این گرامر را به صورت نرمال چامسکی بنویسم  مجبور خواهم بود که داخل این گرامر متغیر هایی تعریف کنم . مثلا قاعده اول متغیر شروع را نگاه کنید  aSb . قسمت aS را من به عنوان متغیر X1 خواهم گرفت و قسمت b را به عنوان متغیر X2 . پس خواهم داشت:

 

S →X1X2

قاعده دوم متغیر شروع هم برای تعریف چامسکی مشکل داره پس من باید این را هم اصلاح کنم قسمت اول aA یعنی a را من با متغیر X3 خواهم شناخت وخود A هم که متغیر هست و فرمول دو متغیر را نقض نخواهد کرد پس خواهم داشت:

S →X1X2|X3A

حالا باید زحمت بکشم و این X هایی که در قاعده ها اوردم بگویم هرکدام چی تولید میکنند.

S →X1X2|X3A

X1→aS

X2→b

X3→a

 

حالا یه سوال به نظرتون قاعده X1 به صورت نرمال چامسکی هست؟ مسلما خیر پس باید این قاعده را هم اصلاح کنیم . من در قاعده X3 گفته بودم که این متغیر سمبل a را تولید خواهد کرد حالا دوباره از این سمبل استفاده خواهم کرد در قاعده X1 . پس تا به الان گرامر من خواه شد:

 

S →X1X2|X3A

X1→X3S

X2→b

X3→a

 

حالا باید خط اخر گرامر سوال را اصلاح کنیم . خوش بختانه در قاعده متغیر شروع ما اینکارو کرده بودیم برای همین از همین قاعده استفاده خواهیم کرد:

 

S →X1X2|X3A

X1→X3S

X2→b

X3→a

A →X3A|a

 

مثال)گرامر زیر را به فرم نرمال چامسکی دراورید.

 

S →A|B

A→aA|λ

B→bB|b

 

این گرامر همون طور که مشاهده میکنید λ، زنجیر دارد پس باید اول ساده سازی کنیم. چون میدونم خیلی به حرفای من گوش میکنید و زیاد تمرین دارید برای همین منم سریع ساده سازی ها را براتون مینویسم و دیگه اعصابتون را خورد نمیکنم.

 

مرحله اول حذف λ:

S →A|B|λ

A→aA|a

B→bB|b

 

مرحله دوم حذف رنجیر های :

 

S →A

S →B

 

پس گرامر من خواهد شد:

 

S →aA|a|bB|b|λ

A→aA|a

B→bB|b

حالا باید این گرامر را به صورت چامسکی بنویسیم. پس خواهیم داشت:

S →X1A|a|X2B|b|λ

X1→a

X2 →b

A →X1A|a

B→X2B|b

فرم نرمال گریباخ:

یک گرامر به فرم نرمال گریباخ خواهد بود اگر و تنها اگرهر قاعده آن به فرم زیر باشد:

A →aα     A ԑV,aԑ∑,α ԑ V  ̽

به زبان ساده تر یعنی هر قاعده متشکل از یک الفبا و دنباله ای از متغیر ها( البته دنباله ای از متغیر ها را میتوان نداشته باشد) باشد.

برای تبدیل یک گرامر به فرم نرمال گریباخ باید قوانین λ، زنجیر، متغیرهای بدون استفاده و بازگشتی از چپ( مربوط به نظریه) را در آن حذف کنیم.

مثال) گرامر زیر را به فرم نرمال گریباخ تبدیل کنید.

S →aSb|AB

A →aA|a

B→bBb|bb

قاعده اول متغیر شروع با الفبا خاتمه پیدا کرده واین خلاف الگوی گریباخ هست پس این قاعده را باید اصلاح کنیم .

S →aSX1

X1→b

قاعده دوم متغیر شروع هم مشکل دارد چون با الفبا شروع نشده. به نظرتون باید چیکار کنم؟ البته باید راهی به نظرتون برسه که زبان گرامر عوض نشود .

نظرتون چیه من قواعد متغیر A را جایگذاری کنم این جوری فکر کنم از مشکلمون کم بشه. پس خواهم داشت:

S →aSX1|aAB|aB

X1→b

A →aA|a

 

متغیر A از لحاظ الگوی گریباخ مشکل ندارد پس خودش را در گرامر خواهیم نوشت. حالا میرسیم به قاعده های متغیر B . خط سوم گرامر . قاعده اول و دوم هردو با الفبا به پایان رسیده  و بیش از یک الفبا در هرقاعده به کار برده شده است پس  مخالف الگوی گریباخ خواهد بود. اما دیگه احتیاج به تعریف متغیر نداریم چون من یه بار برای تعریف سمبل الفبای b از یک متغیر استفاده کرده ام حالا از همون متغیر دوباره استفاده خواهم کرد. پس قاعده های متغیر B من خواهد شد:

 

B →bBX1|bX1

و در نهایت گرامر نهایی من خواهد شد:

S →aSX1|aAB|aB

X1→b

A →aA|a

B →bBX1|bX1

 

 خب دوستان گرامی به پایان چلسه امروزمون رسیدیم امیدوارم تا الان خسته نشده باشید. تمرین فراموشتون نشود . جواب تمرین جلسه قبل که قرار شد برام بفرستید یادتون نرود و...

 

آنچه در نظریه خواهید دید...

جلسه آینده براتون میخوام گرامر های مبهم ، گرامر های خطی و گرامرهای ساده را بگم.

شاد و موفق و سربلند باشید.

تا جلسه آینده خدانگهدار.

دانلود PDF قسمت دوازدهم آموزش نظریه زبان ها و ماشین ها