سوال ۱۱ ) گرامرهایی روی الفبای [tex]\sum =\left \{ a,b \right \}[/tex] بیابید که مجموعه تمام رشته هایی که حداکثر سه a دارند.
میشه این گرامر رو واسش نوشت؟! [tex]S\rightarrow AaAaAaA | AaAaA | AaA[/tex] , [tex]A\rightarrow bA|\lambda[/tex]
سوال ۱۸ فرض کنید الفبا ورودی به شکل [tex]\sum =\left \{ a,b \right \}[/tex] باشد . گرامر زبان زیر را بیابید.
[tex]L=\left \{ w\epsilon \left \{ a,b \right \}^{*} : |n_{a}(w)-n_{b}(w)|=1 \right \}[/tex]
گرامر زبان
[tex]L=\left \{ w:|w|mod3\geqslant |w|mod2 \right \}[/tex]
و این دو سوال و جواب میخواستم واسم توضیح بیشتری بدید
[attachment=7481]
[attachment=7482]
ممنون
سلام
برای سوال اول DFA مربوطه رو کشیدم
[attachment=7485]
همونطور که قابل مشاهده ست و در سوال هم اشاره شده، حداکثر سه a.پس گرامر باید بتونه هیچ a هم نگیره.
[tex]S\rightarrow bS|aA|\lambda[/tex]
[tex]A\rightarrow bA|aB|\lambda[/tex]
[tex]B\rightarrow bB|aC|\lambda[/tex]
[tex]C\rightarrow bC|\lambda[/tex]
۱۸-
توی کتاب برای حالت [tex]n_{a}\left ( w \right )=n_{b}\left ( w \right )[/tex] این راه حل رو ارائه داده
[tex]S\rightarrow SS[/tex]
[tex]S\rightarrow aSb|bSa|\lambda[/tex]
باکمی تغییر میرسیم به
[tex]S_{1}\rightarrow aSS|SaS|SSa|bSS|SbS|SSb[/tex]
[tex]S\rightarrow SS[/tex]
[tex]S\rightarrow aSb|bSa|\lambda[/tex]
[attachment=7507]
[tex]S\rightarrow aA|bA[/tex]
[tex]A\rightarrow aB|bB[/tex]
[tex]B\rightarrow aC|bC[/tex]
[tex]C\rightarrow aD|bD|\lambda[/tex]
[tex]D\rightarrow aE|bE[/tex]
[tex]E\rightarrow aF|bF[/tex]
[tex]F\rightarrow aG|bG[/tex]
[tex]G\rightarrow aH|bH[/tex]
[tex]H\rightarrow aC|bC[/tex]
(۰۸ آبان ۱۳۹۱ ۱۱:۳۴ ب.ظ)hp1361 نوشته شده توسط: ۱۸-یه سوال ؟!!
[tex]S_{1}\rightarrow aSS|SaS|SSa[/tex]
[tex]S\rightarrow aSb|bSa|\lambda[/tex]
میخواستم بدونم اینجور که زبان رو نوشته اختلاف a,b در تمام رشته های پپذیرفته شده یک باشه (!)
فکر کنم باید S1 چند حالات رو برای مواقعی که b ها بیشتر a ها هستند اضافه کرد!
[tex]S_{1}\rightarrow aSS|SaS|SSa|bSS|SbS|SSb[/tex]
سلام
توی سوال گفته شده که تمام w هایی که اگر تعداد a ها را منهای تعداد b ها کنیم نتیجه برابر ۱ شود و این بدان معنی است که تعداد a ها دقیقاً یکی بیشتر از b ها شود.
برای مقایسه تعداد a ها با تعداد b ها تنها یک راه داریم و آن این است که به ازای یک a یک b هم پذیرفته شود.حالا برای اینکه تعداد a یکی بیشتر از b باشد ۳ حالت داریم.ابتدای رشته است، میانه رشته است یا انتهای رشته که با سه حالت s1 آنرا انجام دادیم.
مثال:
abbabaa در این مثال جفت جفت ab یا ba رو کنار بذار.تنها یک a میماند.تست ترتیب تولیدab یا ba هم با خودتون.
توی پرانتز(اوتوماتای mod3>=mod2 حالات پایانیش اصلاح شد)
(۱۰ آبان ۱۳۹۱ ۰۷:۵۲ ب.ظ)hp1361 نوشته شده توسط: توی سوال گفته شده که تمام w هایی که اگر تعداد a ها را منهای تعداد b ها کنیم نتیجه برابر ۱ شود و این بدان معنی است که تعداد a ها دقیقاً یکی بیشتر از b ها شود.اوههه اصلا حواسم نبود که این علامت قدر مطلق نیست
عجب اشتباه زشتی!
سلام
فکر کنم من اشتباه کردم
حق با شماست.تعداد a و b در رشته w یک عدد است پس فکر کنم معنیش همون قدر مطلق باشه که شما بدرستی متوجه اش شده اید.
پست ها رو اصلاح کردم.
سلام. سوال ۱۸ یه اشکال کوچیک داره. aabbbbaabaabbbbaa رو تولید نمیکنه. توی S مشکل داره. بهتر بود مینوشتید S->SaSbS|SbSaS|y.
برای سوالاتی که اسکن کردید هم یه توضیح میدم. زبانهای منظم حافظه محدود دارن. هر زبان که حافظه نامحدود نیاز نداشته باشه منظمه. هر زبان که تعداد محدود رشته رو شامل میشه منظمه. توی مثال اولتون فقط رشته های با طول مشخص رو خواسته. یعنی حافظه به اندازه ۳ و اگه همین حافظه رو برای هر n محدود میخواست باز هم منظم بود. حالا چه میخاد مضرب n باشه، چه متممش و چه مثلاً دارای باقی مانده ۲ یا ۷ و یا ۲۴ نسبت به n. مثال دومتون هم عبارت منظم زبان رو نوشته. هر زبان که با عبارت منظم بیان بشه منظمه. میشه گفت این زبان فقط ۵۰۱ رشته رو قبول میکنه پس منظمه. میشه گفت چون طول رشته های پذیرفته شدش بیشتر از ۳ نیست پس منظمه. میشه براش یه dfa کشید پس منظمه.