دوستان من تازه عضو شدم امیدوارم بتونم از کمکاتون استفاده کنم، من این ترم نظریه دارم تو تمرینای لینز به یک مشکلی برخوردم:
تو کتاب لینز ویرایش چهارم بخش ۳-۳ تمرین تمرین ۱۱ گفته: یک گرامر منظم برای زبان
{زوج باشدL={an bm | n+m
a به توان n وb به توان m )میشه راهنمایی کنید تو حل تمرینش اول نوشته S→D |Aa
این گرامر نمی تونه منظم باشد به خاطر D.
لطفا از لینک ارسال پاسخ جدید استفاده کنید که بتونید فرمولها رو در TEX بنویسید.
[tex]a^nb^m| n m: Even[/tex]
n+m وقتی زوج است که یا n و m هر دو فرد باشند یا هردو زوج
پس شما کافی است گرامری بنویسید که یا [tex]a^nb^m | n,m even[/tex]
یا [tex]a^nb^m | n,m odd[/tex]
را تولید کنید.
[tex]S\rightarrow aA|D[/tex]
[tex]A\rightarrow aaA|B[/tex]
[tex]B\rightarrow bbB|b[/tex]
[tex]D\rightarrow aaA|C[/tex]
[tex]C\rightarrow bbB|\lambda[/tex]
که استفاده از قانون D منجر به تولید رشته‌ها با m,n زوج است.
گرامر منظم است و شما میتوانید برای آن DFA رسم کنید.(کلا زوج و فرد بودن رو با استفاده از تغییر وضعیت میتوان مشخص کرد)
اینکه گفتین D باعث شده که گرامر منظم نباشه رو من متوجه نمیشم!!!
اینکه داریم [tex]A\rightarrow aaA[/tex]
را میتونید به این صورت هم بنویسید که شاید منظم بودنش رو بهتر بشه درک کرد( اینکه گرامر خطی است)
[tex]A\rightarrow aX[/tex]
[tex]X\rightarrow aA[/tex]
این که گفتید D مشکل داره درست نیست احتمالا منظور شما این هست که در تعریف گرامر های منظم این شکل رو که S-->D نداریم . گرامر‌ها می تونن خطی از راست باشند و خطی از چپ و یک گرامر منظم گرامری است که همه قواعد آن یا خطی از راست باشند یا خطی از چپ . در ضمن در یک گرامر منظم حداکثر یک متغیر در سمت راست قواعد ظاهر می شود و علاوه بر این متغیر مورد نظر باید همواره آخرین نشانه سمت راست یا آخرین نشانه سمت چپ باشد برای همین هم جوابی که دوست عزیزمون براتون ارسال کردن کاملا صحیح است
ممنون از جوابتون
این گرامرو من دیدم، مشکل من در خط اول یعنی جایی که احتمالا مفهومو اشتباه درک کردم .
[tex]S \to \ aA/D[/tex]
ببینین تو تعریفش اینطوری نیست یعنی نمیشه یک متغیر غیر نهایی مثل [tex]D[/tex]
به تنهایی در سمت راست بیاد .
[tex]A \to \ xB[/tex]
[tex]A \to \ x[/tex]
من اینطور متوجه شدم فقط متغیر نهایی می تواند به تنهایی در سمت راست بیاد. اشتباه متوجه شدم؟؟؟؟؟؟؟؟؟؟؟؟؟
به قوانینی که بصورت
[tex]S\rightarrow D[/tex]
هست قوانین یکه گفته میشه که بی فایده هستند شما میتونید آنچه در سمت راست D قرار دارد جایگزین آن کنید.(فقط برای درک بهتر از این نوع قواعد استفاده میشه)
[tex]S\rightarrow aA|aaA|C[/tex]
مجددا به جای C نیز سمت راستش را جایگزین میکنید.( رفع ابهام و حذف قوانین یکه )
این قاعده معادل استفاده از لاندا در NFA است یعنی شما بدون خواندن هیچ سمبلی تغییر وضعیت میدهید مثل اینجا که بدون خواندن هیچ سمبلی از S به D تغییر وضعیت میدهید. که تناقضی با منظم بودن گرامر ندارد. زیرا وجود NFA برای یک زبان نشان دهنده منظم بودن آن است.
دقت کنید که در
[tex]A\rightarrow xA[/tex]
x میتواند شامل هر تعداد پایانه (سمبل )باشد.(به پست قبل مراجعه کنید)
ممنون از راهنمایی هاتون، مفهومو درک کردم .
میشه اینجوری هم جواب داد؟؟؟؟
[tex]S\rightarrow bA|aB|\lambda[/tex]
[tex]A\rightarrow bS|aC[/tex]
[tex]B\rightarrow aS|bC[/tex]
[tex]C\rightarrow aA|bB|\lambda[/tex]
(۲۴ فروردین ۱۳۹۰ ۰۹:۴۶ ب.ظ)afagh1389 نوشته شده توسط: لطفا از لینک ارسال پاسخ جدید استفاده کنید که بتونید فرمولها رو در TEX بنویسید.
[tex]a^nb^m| n m: Even[/tex]
n+m وقتی زوج است که یا n و m هر دو فرد باشند یا هردو زوج
پس شما کافی است گرامری بنویسید که یا [tex]a^nb^m | n,m even[/tex]
یا [tex]a^nb^m | n,m odd[/tex]
را تولید کنید.
[tex]S\rightarrow aA|D[/tex]
[tex]A\rightarrow aaA|B[/tex]
[tex]B\rightarrow bbB|b[/tex]
[tex]D\rightarrow aaA|C[/tex]
[tex]C\rightarrow bbB|\lambda[/tex]
که استفاده از قانون D منجر به تولید رشته‌ها با m,n زوج است.
گرامر منظم است و شما میتوانید برای آن DFA رسم کنید.(کلا زوج و فرد بودن رو با استفاده از تغییر وضعیت میتوان مشخص کرد)
اینکه گفتین D باعث شده که گرامر منظم نباشه رو من متوجه نمیشم!!!
------------------
[tex]C\rightarrow bbB|\lambda[/tex] باعث میشد تعداد b ها فرد بشه.
[tex]S\rightarrow aA|D[/tex]
[tex]A\rightarrow aaA|B[/tex]
[tex]B\rightarrow bbB|b[/tex]
[tex]D\rightarrow aaA|C[/tex]
[tex]C\rightarrow bbC|\lambda[/tex]
با تشکر از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
[quote='saharp' pid='53341' dateline='1321031110']
میشه اینجوری هم جواب داد؟؟؟؟
[tex]S\rightarrow bA|aB|\lambda[/tex]
[tex]A\rightarrow bS|aC[/tex]
[tex]B\rightarrow aS|bC[/tex]
[tex]C\rightarrow aA|bB|\lambda[/tex]
نه خیر این جواب درست نیست. صورت سوال [tex]a^nb^m| n m: Even[/tex] بوده.
که رشته های , ab,aa,bb,aaaa,bbbb,aabb,
, [tex]\lambda[/tex] , سایر رشته هایی به این فرمت رو تولید میکنه.
پس گرامر شما به دلیل تولید رشته های ناخواسته ای مثل : ba, baba,bbaa,... رد میشه.
البته گرامر شما میتونه جواب این زبان منظم باشه:
[tex] (a^n b^m)* | n m: Even[/tex]
یا این یکی:
[tex] (a b)* [/tex] با شرط اینکه جمع تعداد a و تعداد b زوج باشد.
گرامر این زبان منظمه. یک حافظه محدود میخاد.
[tex]S\to aaS|aA|B[/tex]
[tex]A\to bbA|b[/tex]
[tex]B\to bbB|\lambda[/tex]
[tex]A\to bbA|b[/tex]
[tex]B\to bbB|\lambda[/tex]
اینم گرامر راست خطیش. nfa رو هم میشه از روی گرامر ساخت.