{a^n b^m c^i d^j : n+m>=i+j }
با عرض سلام خدمت همه دوستان عزیز.
به نظرتون ای مستفل از متن هستش؟
اگه جهت نامساوبی برعکس میشد چه تغییری می کرد؟
ممنون از کمکتون.
به نظر من فرقی نمیکنه جهت نامساوی چطور باشه.مهم اینه که تعداد حروف الفبا به هم وابسته است و باید این وابستگی را با پشته پیاده سازی کرد.به طوریکه تعداد حروف وارد شده به پشته شمارش بشه
(۲۶ بهمن ۱۳۹۰ ۱۲:۰۸ ب.ظ)fatima1537 نوشته شده توسط: به نظر من فرقی نمیکنه جهت نامساوی چطور باشه.مهم اینه که تعداد حروف الفبا به هم وابسته است و باید این وابستگی را با پشته پیاده سازی کرد.به طوریکه تعداد حروف وارد شده به پشته شمارش بشه
شما فکر کنید این دوتا رشته رو خواهیم داشت
aaabbbccdd
آیا این با اولی پذیرفته میشه؟
جواب منفی هستش
اما میشه برای این pda ساخت
aabbccdddd
نظر شما چیه؟
به نظر من اگه با ab پشته رو پر کنیم و با c و d پشته رو خالی در اخر به جایی می رسیم که یا پشته خالیه یا قسمتی از پشته پره که با پیمایش لاندا می تونیم پشته رو خالی کنیم. اما فکر نمی کنم" معین" هم باشه
(۲۶ بهمن ۱۳۹۰ ۰۱:۵۷ ب.ظ)anyone نوشته شده توسط: به نظر من اگه با ab پشته رو پر کنیم و با c و d پشته رو خالی در اخر به جایی می رسیم که یا پشته خالیه یا قسمتی از پشته پره که با پیمایش لاندا می تونیم پشته رو خالی کنیم. اما فکر نمی کنم" معین" هم باشه
اما اگه تعدا د a , b ها بیشتر باشن باز میشه با لاندا ردشون کرد. اما اگه تعداد c, d ها بیشتر باشن نمیشه. با غیر قطعی میشه به نظرتون؟
(۲۶ بهمن ۱۳۹۰ ۰۱:۰۷ ب.ظ)lonelyforever نوشته شده توسط: شما فکر کنید این دوتا رشته رو خواهیم داشتاگر منظورتون از اولی یعنی همون {a^n b^m c^i d^j: n+m>=i+j } که بله پذیرفته میشه .ولی برای اینکه رشته هایی که در این شرط صدق نمیکنند توسط گرامر پذیرفته نشن باید یک ماشین پشته ای داشته باشیم که وقتی داره علامتهای مربوط به cوd را وارد پشته میکنه به ازای هرکدوم ازCیا D، یک A یا B از پشته حذف کنه، اگر دیگر AیاB نبود نتونه چیزی رو خارج کنه و به حالت پایانی بره(فکرکنم با ۲ پشته حل بشه)
aaabbbccdd
آیا این با اولی پذیرفته میشه؟
جواب منفی هستش
(۲۶ بهمن ۱۳۹۰ ۰۱:۰۷ ب.ظ)lonelyforever نوشته شده توسط: اما میشه برای این pda ساختاین زبان توسط {a^n b^m c^i d^j: n+m>=i+j } پذیرفته نمیشه اما اگر جهت علامت تغییر کنه یعنی باشه: {a^n b^m c^i d^j: n+m<=i+j } اونوقت این رشته توسط این زبان پذیرفته خواهد شد و میشه برای این زبان هم pda ساخت
aabbccdddd
برای m+n>=i+j داریم:
[tex]S\to aSd|aS|A|B[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|bC|\lambda[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|bC|\lambda[/tex]
ماشین پشته ایشم یه تعداد a میخونه و به ازای هرکدوم ۱ پوش میکنه. بعد به ازای هر b یک ۱ پوش میکنه. به ازای هر c یک ۱ پاپ میکنه و به ازای هر d یک ۱ پاپ میکنه. مسلماً برای پاپ کردن باید محتوای پشته ۱ باشه. درغیر اینصورت ماشین از حالت پایانی خارج میشه. حالاتی که c و d رو ماشین میخونه و ۱ پاپ میکنه حالات پایانین.
برای m+n<=i+j داریم:
[tex]S\to aSd|Sd|A|B[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|Cc|\lambda[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|Cc|\lambda[/tex]
ماشین پشته ایشم یکم فرق میکنه. به ازای اولین a یا b میتونیم ۰ پوش کنیم. حالت پایانی هم میشه رسیدن به ۰ یا $ با شرط بهم نخوردن ترتیب رشته میشه.
(۲۶ بهمن ۱۳۹۰ ۰۵:۵۱ ب.ظ)Lakikharin نوشته شده توسط: ماشین پشته ایشم یه تعداد a میخونه و به ازای هرکدوم ۱ پوش میکنه. بعد به ازای هر b یک ۱ پوش میکنه. به ازای هر c یک ۱ پاپ میکنه و به ازای هر d یک ۱ پاپ میکنه. مسلماً برای پاپ کردن باید محتوای پشته ۱ باشه. درغیر اینصورت ماشین از حالت پایانی خارج میشه. حالاتی که c و d رو ماشین میخونه و ۱ پاپ میکنه حالات پایانین.پس چطور بشماره تا تعداد cوd کمتر یا مساوی aوb باشه؟
وقتی c,dها بیشتر باشن اونموقع توی پشتمون دیگه ۱ نمیمونه. توی حالت پایانی هستیم ولی رشتمون تموم نشده؛ پس رشته رو قبول نمیکنه.
(۲۶ بهمن ۱۳۹۰ ۰۵:۵۱ ب.ظ)Lakikharin نوشته شده توسط: برای m+n>=i+j داریم:
[tex]S\to aSd|aS|A|B[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|bC|\lambda[/tex]
ماشین پشته ایشم یه تعداد a میخونه و به ازای هرکدوم ۱ پوش میکنه. بعد به ازای هر b یک ۱ پوش میکنه. به ازای هر c یک ۱ پاپ میکنه و به ازای هر d یک ۱ پاپ میکنه. مسلماً برای پاپ کردن باید محتوای پشته ۱ باشه. درغیر اینصورت ماشین از حالت پایانی خارج میشه. حالاتی که c و d رو ماشین میخونه و ۱ پاپ میکنه حالات پایانین.
برای m+n<=i+j داریم:
[tex]S\to aSd|Sd|A|B[/tex]
[tex]A\to aAc|C[/tex]
[tex]B\to bBd|C[/tex]
[tex]C\to bCc|Cc|\lambda[/tex]
ماشین پشته ایشم یکم فرق میکنه. به ازای اولین a یا b میتونیم ۰ پوش کنیم. حالت پایانی هم میشه رسیدن به ۰ یا $ با شرط بهم نخوردن ترتیب رشته میشه.
پس شما میگید که جفت اینها مستقل از متن هستند؟
هردو مستقل از متنن. چون فقط یه شرط برای مقایسه دارن و محدودیتی در حداکثر تعداد مقادیرمون نداریم. m+n>=i+j تنها شرط ماست. درکل رشته هایی به این فرم که فقط یه مقایسه دارن مستقل از متنن. نمونه هاش اینا هستن:
[tex]a^mb^nc^pd^q;m q\leq n p[/tex]
[tex]a^mb^nc^pd^q;m p\leq n q[/tex]
[tex]a^mb^nc^pd^q;2m 3n\geqslant p q[/tex]
[tex]W|n_a(W)\leq 2n_b(W)[/tex]
[tex]a^mb^nc^pd^q;m p\leq n q[/tex]
[tex]a^mb^nc^pd^q;2m 3n\geqslant p q[/tex]
[tex]W|n_a(W)\leq 2n_b(W)[/tex]
ولی توجه کنید که همشون مقایسه مقداره نه زوج و فرد و مضرب مثلاً ۵ بودن. اگه میگفت باقی مانده m+n و i+j در تقسیم با ۵ برابره اون موقع دیگه منظم میشه. چون با یک حافظه محدود میشه طراحیش کرد.