با سلام بر دوستان گل و عزیز
این درس ما را پیر کرد: لطفا راهنمایی کنید:
گرامر زیر را به فرم چامسکی و گریباخ تبدیل کنید؟؟
هر کدام را که بلدید لطفا انجام وتوضیح بدهید!
[tex]S\rightarrow aABC|a[/tex]
[tex]A\rightarrow aA|a[/tex]
[tex]B\rightarrow bcB|bc[/tex]
[tex]C\rightarrow cC|c[/tex]
سپاس
این سوال کلیه
...خب فرم نرمال چامسکی میدونید که به چه صورت هست؟سمت راست قاعده مون باید ۲تا علامت غیر نهایی(دوتا علامت بزرگ) و یا یک علامت نهایی(یک حرف کوچیک) داشته باشیم...حالا ما هر گرامر که داشته باشیم باید برای همه شون این قواعد رو رعایت کنیم...
S->aABC/a ابتدا از گرامر اول شروع میکنیم...
S->EC "توضیحات">> aAB را حرف E در نظر میگیریم.
E->DB "توضیحات" aA را حرف D در نظر میگیریم.
D->FA "توضیحات" a را جرف F در نظر میگیریم.
F->a و در آخر F می رود به یک علامت نهایی..
******
S->a این که خودش چامسکیه...
*****
A->aA/a مانند بالا .....
A->XA
X->a
*****
A->a خودش چامسکیه....
*****
B->BcB/bc مانند بالا....
B->YB
Y->GK
K->c
G->b
*******
B->GK قسمت دوم B را مانند مراحل بالا...
K->c
G->b
******
C->cC/c مانند مراحل بالا...
C->LC
L->c
C->c خودش چامسکیه...
=====================
گریباخ رو هم ایشالله دوستان بگن(ما بریم شام :دی)
اگر اشتباه گفتم دوستان تصحیح کنن
[attachment=8536]
متشکر دوست عزیز:زیاد متوجه نشدم:من یک عکس میزارم :لطفا دوستان طبق ان توضیح بدهند!(فعلا چامسکی را )
سپاس
سلام. لطفاً قبل از طرح سوال یکدور کتاب درس رو مرور کنید. صحبت های دوستمون jameshenas کامل بود. توی چامسکی گرامرمون فقط باید به یکی از فرم های [tex]A\to BC|a[/tex] باشه. یعنی یا به دوتا غیرپایانه یا یک پایانه. برای S قانون اول که با قرمز مشخص شده بفرم چامسکی نیست. ولی دومی که خط قرمز نداره مشکلی نداره. باید قسمت اول گرامر رو به شکل دوتا غیرپایانه بنویسیم. توی عکستون اولین پایانه رو T2 و بقیه رو T1 درنظر گرفته. پس داریم:
[tex]T_1\to ABC[/tex]
[tex]T_2\to a[/tex]
حالا T1 هم بفرم چامسکی نیست. اینبار AB رو T3 میگیریم. با اینکار این گرامرهامون بفرم چامسکی تبدیل میشن. برای بقیه غیر پایانه ها هم همین کارو کرده. هر کدوم که به یک پایانه و دو غیرپایانه نمیرن بفرم دو غیرپایانه تبدیل میکنه.
متشکر:گریباخ چی میشه؟؟
توی گریباخ داریم [tex]A \to bCDEF ...[/tex] (A \to bCDEF) یعنی هر غیر پایانه به یک پایانه و در ادامه به هر تعداد غیرپایانه میره. توی گرامرتون فقط [tex]B \to bcB | bc[/tex] (B \to bcB | bc) بفرم گرباخ نیست. چون در ابتدا دوتا پایانه داره. (درسته؟) تنها کاری که باید بکنیم اینه که یه غرپایانه مثل [tex]T \to c[/tex] (T \to c) تعریف کنیم. بعد B رو بفرم [tex]B \to bTB|bT[/tex] (B \to bTB|bT) تغییر بدیم.
متشکر: ولی من زیاد متوجه نشدم: لطفا ان مثال بالایی را حل کنید تا جمیعا بفهمیم
در ضمن:یک سئوال: مرجع من سودکمپ هست!! چرا مباحثی که توی کتاب سود کمپ هست با کتاب لینز بسیار فرق داره!!! مثلا توی کتاب سودکمپ حذف متغیر بازگشتی چپ داریم ولی توی کتاب لینز چنین مبحثی نیست!!! کلا خیلی مباحث این دو کتاب باهم فرق دارند!! ایا کتابی وجود داره که تمام مباحث را پوشش داده باشه و در ضمن توضیح کامل هم داده باشه!!! مثلا: راه حل فرم نرمال چامسکی را با یک مثال جامع توضیح داده باشه !!
سپاس
کسی نظری نداره!!
خوب منم مثال شما رو حل کردم. فرم کلی گریباخ رو نوشتم. گفتم که همشون غیر از یکی گریباخن. اون یکی رو گریباخ کردم.
حذف بازگشتی از چپ رو ما توی کامپایلر داشتیم. زیاد سخت نیست.