a^n b^m c^k d^p
m+p=n=k
چرا زبان بالا مستقل از متنه؟یه تحلیل بدید،مثلا وقتیaرو دیدی یه Aپوش میکنیم و....
ممنون
چرا زبان a^n b^j c^n c^j مستقل از متن هست ولی این زبان نه: a^n b^j a^n b^j
(۱۱ دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط: چرا زبان a^n b^j c^n c^j مستقل از متن هست ولی این زبان نه: a^n b^j a^n b^j
این زبانو a^n b^j c^n c^j میشه به این شکل نوشت:
a^n b^j c^j c^n
اگر a اومد که پوش میشه، b اومد پوش میشه تو استک، اگه c اومد تا موقعی که b تو استک میبینه، pop میکنیم،اگر bها تموم شد و بازم c میومد، تا موقعی که استک a داره pop میکنیم. اگرc تموم شد و بازم تو استک a داشتیم که reject میشه.و همینطور حالات دیگه ای هم میشه واسه عدم پذیرش رشته در نظر گرفت.
اما تو زبان دوم نیاز به دو حافظه داریم.
(۱۱ دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط: a^n b^m c^k d^pسوال منم هست
m+p=n=k
(۱۱ دى ۱۳۹۰ ۰۶:۵۵ ب.ظ)NoOne نوشته شده توسط:(11 دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط: a^n b^m c^k d^pسوال منم هست
m+p=n=k
به نظرم شکل و شمایل این زبان بیشتر به حساس به متن بخوره تا مستقل از متن .
با این حال مطمئن هستین مستقل از متنه؟
[tex]a^{n}b^{m}c^{n}d^{p} , n=p k[/tex]
سوال آزمون پارسه بوده
جواب خود پارسه برای این سئوال چی بوده؟ گرامر؟ ماشین پشته ایی؟
چیزی ننوشته فقط نوشته میشه ماشین پشته ای واس گزینه ۳ کشید
اما بنظر من گزینه ۴ درسته
(۱۱ دى ۱۳۹۰ ۰۷:۴۵ ب.ظ)hadi_m نوشته شده توسط:(11 دى ۱۳۹۰ ۰۶:۵۵ ب.ظ)NoOne نوشته شده توسط:(11 دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط: a^n b^m c^k d^pسوال منم هست
m+p=n=k
به نظرم شکل و شمایل این زبان بیشتر به حساس به متن بخوره تا مستقل از متن .
با این حال مطمئن هستین مستقل از متنه؟
[tex]a^{n}b^{m}c^{n}d^{p} , n=p k[/tex]
این زبان مستقل از متن نیست!!!!!
این بدیهیست!
با توجه به سوال پارسه شرط M+P=N+K است که ماشین پشته ای می توان طراحی کرد
لطفا دقت کنید شرط با توجه به سئوال M+P==N+K هست نه این M+P=N=K
و طبق فرامایشات دوست عزیزمون _azarbarzin این زبان مستقل از متن هست و به راحتی میتوان برای ان ماشین پشته ایی طراحی کرد اما زبان با اون شرایطی که نوشتین یک زبان حساس به متن هست وبا پشته نمیتوان شرط رو چک کرد .
(۱۲ دى ۱۳۹۰ ۱۲:۳۶ ب.ظ)hadi_m نوشته شده توسط: لطفا دقت کنید شرط با توجه به سئوال M+P==N+K هست نه این M+P=N=Kاز همه به خاطر اشتباه تایپی که کردم معذرت می خوام
و طبق فرامایشات دوست عزیزمون _azarbarzin این زبان مستقل از متن هست و به راحتی میتوان برای ان ماشین پشته ایی طراحی کرد اما زبان با اون شرایطی که نوشتین یک زبان حساس به متن هست وبا پشته نمیتوان شرط رو چک کرد .
(۱۲ دى ۱۳۹۰ ۰۳:۵۸ ب.ظ)NoOne نوشته شده توسط: ممکنه بیشتر توضیح بدید چطور مستقل از متنه؟و اینکه چرا گزینه ۴ غلطه؟
aها را وارد پشته می کنیم
۱- اگر تعداد bها کمتر از a بود به ازای هر b یک a پاپ می کنیم (بعد از خواندن bها هنوز در پشته a داریم) و سپس cها را پوش میکنیم
در پایان به ازای هر d اگر روی پشته a بود a و اگر c بود c پاپ می کنیم
با تمام شدن رشته ،پشته هم خالی می شود و رشته پذیرفته می شود
مثال a^2b^3c^4d^6
۲- اگر تعداد bها بیشتز از a بود به ازای هر b یک a پاپ می کنیم بعد از پاپ همه aها بقیه bها پوش می شود و سپس cها را پوش میکنیم
در پایان به ازای هر d اگر روی پشته c بود c و اگر b بود b پاپ می کنیم
با تمام شدن رشته ،پشته هم خالی می شود و رشته پذیرفته می شود
مثال a^3b^2c^4d^5
البته قسمت دومش رو من یه اصلاح کنم
۲-- اگر تعداد bها بیشتز از a بود به ازای هر b یک a پاپ می کنیم بعد از پاپ همه aها بقیه bها پوش می شود و
سپس به ازای هر C یک b از پشته pop می کنیم وقتی تعداد bها تموم شد، C های باقیمانده رو push می کنیم.
در پایان به ازای هر d یک C را Pop می کنیم .
با تمام شدن رشته ،پشته هم خالی می شود و رشته پذیرفته می شه.
در مورد گزینه چهار هم که گفته:
مکمل هر زبان مستقل از متن یک زبان بازگشتی است ولی مستقل از متن نیست .
قسمت اول جمله درسته ولی وقتی می گه مستقل از متن نیست درست نیست
چون زبان های مستقل از متن تحت عمل مکمل بسته نیست ولی وجود داره زبانی که مستقل از متن باشه و مکملش هم مستقل از متن باشد .
من ۲ رو متوجه نمیشم چه جوری وقتی هنوز پشته خالیه به ازای هر b یک a پاپ می کنیم؟مثلا وقتی داریم a^3 b^6 c^5 d^2 مااول باید a هارو ببینیم و تا aها رو نبینیم که نمیتونیم سراغ bها بریم
وقتی پشته خالیه میتونیم b رو پوش کنیم. اونوقت اول c های اول رو با b های پسته میزنیم و بعد c هارو پوش میکنیم. مرحله آخر هم زدن a و c های پشته با dهاست.
میشه از گرامر هم استفاده کرد:
[tex]S \to aSd | ABC[/tex]
[tex]A \to aAb | \lambda[/tex]
[tex]B \to bBc | \lambda[/tex]
[tex]C \to cCd | \lambda[/tex]
[tex]A \to aAb | \lambda[/tex]
[tex]B \to bBc | \lambda[/tex]
[tex]C \to cCd | \lambda[/tex]