گرامرهای مبهم خطی ساده

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

سلام محمدرضا احمدآبادی هستم با جلسه سیزدهم نظریه زبان ها در خدمتتون هستم.

حالتون چطوره ؟ خوب هستید ؟ منم خوبم. امروز قصد دارم  پرونده گرامر هارا براتون ببندم و اخرین مبحث های گرامر را براتون بگم . امروز میخوام براتون گرامر های مبهم ، گرامر های خطی و گرامر های ساده را بگم .

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

تعداد سمبل b این زبان باید برابر با مجموع تعداد سمبل های a,c باشد. پس گرامر ما خواهد شد:

S → aSb|A

A →bAc| λ

 

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

 

گرامر درست این زبان خواهد بود:

S →AB

A →aAb|λ

B→bBc|λ

 

[Click and drag to move]

 


حالا  دیدید نظریه میتونه شیرین باشه و اگر تمرین داشته باشید میتوانید حتی مچ من را هم بگیرید.

قابل توجه همه شما یکی از اعضای همین کانال که از قضا آموزش ها را دنبال میکنه متوجه این اشتباه من شد و منو مطلع کرد.

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

S →BS|B

B →b

 

[Click and drag to move]

 

 و اما بریم سراغ مبحث امروزمون.

گرامر مبهم:

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

مثال) گرامر زیر یک گرامر مبهم است:

S →SS|ab|λ

مثلا برای رشته ab دو اشتقاق خواهیم داشت:

S →SS →S →ab

S →SS→SSS →SabS →abS→ab


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

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

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

مثال) گرامری که در بالا در براتون گفتم را ببینید، گراف تجزیه آن خواهد شد:

آموزش نظریه زبان ها و ماشین ها


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

شاید براتون سوال پیش اومده که گرامر مبهم چه فرقی با بقیه گرامر ها داره؟

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

مثلا ، گرامری برای تولید عبارت های ریاضی  شامل عملگرهای +و- و عملوند های تک رقمی داریم که به صورت زیر است:

E →E+E|E-E|0|1|2|….|9|

[Click and drag to move]

حالا من میخوام حاصل عبارت  9-4+3 را بدست بیارم . برای بدست آوردن جواب این عبارت من دوراه دارم

نظریه زبان ها  و ماشین ها


 

آموزش نظریه زبان ها و ماشین ها


که جواب درخت اول خواهد شد 2 و جواب درخت دوم خواهد شد 8.   حالا یه لحظه باخودتون فکر کنید که کامپیوتر هستید وقواعد تقدم عملگرهارا نمیدونید و فقط این گرامر رابرای جمع و تفریق به شما داده اند  حالا کدوم جواب را به مخاطب نشان خواهید داد؟

اما این گرامر را میخوام براتون درخت تجزیه اش را بکشم تا به عنوان یه مثال اضافه برای درخت تجزیه ازمن داشته باشید .

نظریه ماشین ها و زبان ها

 ابهام یکی از ویژگی های گرامر است ، یعنی شاید بتوان برای زبانی که گرامر مبهم برایشان نوشته شده است گرامر غیر مبهم نیز ارائه کرد ، اما بعضی از زبان ها هستند که به هیچ عنوان نمیتوان گرامر غیر مبهمی برایشان ارائه کرد که به آن ها گرامر های ذاتا مبهم میگویند.

گرامر های خطی:

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

مثال)

نظریه زبان ها و ماشین ها

گرامر های ساده:

 

نظریه زبان ها و ماشین ها

 

به زبان عامیانه اگه بخوام تعریف کنم این طوری باید بگم  : اگر یک متغیر چندین قاعده تولید داشته باشد که هر قاعده با یک سمبل الفبا اغاز شده باشد ، این قوانین باید این شرط راهم داشته باشند که اگر قاعده ای با سمبلی ( مثلا a) شروع شد دیگر هیچ قاعده ای از این متغیر نباید با آن سمبل ( a ) شروع شود .مثال) در مورد گرامر های G1,G2 کدام گزینه درست است؟

G1= S →aS |bSS|c

G2 = S →aS|bSS|aSS|c

الف) G1 ساده ولی G2 غیر ساده است.

ب) G1 غیر ساده و G2 ساده است.

ج) هردو گرامر ساده اند.

د) هر دو گرامر غیر ساده اند.


پاسخ همون طور که خودتون هم فهمیدید گزینه الف میشود.

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

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

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

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