سلام
این زبان در تست ساله ۷۷ اومده ظاهرا مستقل از متن هست.
میشه یکی از دوستان توضیح بده اینو چطور میشه با پشته پذیرش کرد؟
ممنون میشم
[tex]l1={a^{p}b^{q}a^{p}b^{s}}|p,q,s\geq 0}[/tex]
کافیه این زبان رو به صورت الحاق دو زبان زیر در نظر بگیرید:
[tex]L=\{a^{p}b^{q}a^{p}\}.\{b^{s}\}[/tex]
خیلی بدیهیه که میشه برای چنین زبانی یک ماشین پشته ای طراحی کرد
چطور میشه از رو پشته p تا a گذاشت(یا برداشت) در صورتی که بالای پشته ما ابتدا q تا b داریم؟ به تعداد p دسترسی نداریم که!!!
ببینید از اون جایی که توانهای b و a بهم ربطی ندارن یعنی رابطه ای بین اونا برقرار نیست با پشته قابل پیاده سازیه شما بعد از این که pتا a رو روی پشته قرار دادید به نظرم لازم نیست bها رو روی پشته بذارید چک می کنید زمانی که دوباره به a رسیدید به ازا هر a یک a ازبالای پشته برمیدارید . بعد هم می تونید هر تعدادb داشته بتشید.
اگه اشتباه بود دوستان اصلاح کنند
ابتدای کار اگر a اومد، آن را درپشته پوش میکنیم،اگر b اومد دو حالت داره: ممکنه این b، اولین حرف رشته باشه، که به هر تعدادی که نیازه از ورودی میپذیره،(و میتوان b^q و b^s رو باهم در نظر گرفت) اما تو پشته تغییری نمیدیم،اگر به پایان رشته رسیدیم و تو استک چیزی نبود رشته پذیرفته میشه، اما اگر b بعد از a اومده باشه،به هر تعداد که بیاد از ورودی میگیریم و در پشته تغییری نمیدیم، تنها فرقش با حالت قبل اینه که ممکنه، بعد از a، b ببینه،که در این صورت تا جایی که در پشته a هست و a میاد از پشته پاپ میکنیم،اگر پشته خالی شد، و رشته تموم شد که پذیرفته میشه، اما بعد اگر b اومد و پشته خالی بود که میپذیره و تو استک چیزی نمیریزه، تا به پایان رشته برسیم .
هر رشته ای که جز زبان باشه میتونیم با این ساختار پیادش کنیم.
نمیدونم فهمیدم یا نه!!!
یعنی منظورتون این شد که اگه بعده b، a اومد b رو تو پشته وارد نمیکنیم!! آره؟ مگه نباید هرچی اومد باید با پشته پردازش بشه؟
ممنون از وقتی که گذاشتین!!
حتما نباید در پشته چیزی اضافه بشه، میتونیم تو حرکتمون به جاش لاندا بذاریم که چیزی توش اضافه نمیشه.
مثلا اگر یه ماشین dfa رو بخواهیم با npda پیاده سازی کنیم، مثل حالتی که فرضا میخواستیم ماشین حاصل از اشتراک یک زبان منظم(dfa) و زبان مستقل از متن(npda) رو تولید کنیم،برای اثبات مستقل از متن بودن زبان حاصل میگفتیم dfa رو میشه با ساختار پشته پیاده سازی کرد اما بدون اینکه چیزی تو پشته اضافه بشه....
اگه ابهامی بود بفرمایید که توضیح بیشتر بدم.