سلام کسی می تونه برای زبان زیر Npda رسم کنه؟تو تمرین ۴ بخش ۱ فصل ۷ ویرایش ۴ لینزه (صفحه ۱۷۲)
لطفا نگید از حل تمرینش ببین چون حلش رو ندارم فقط جواب سوال رو بگید.(با شکل)
کد:
L = {w:2na(w)<nb(w)<3na(w)}علامت مساوی نداره؟ (کوچیکتر مساوی یا بزرگتر مساوی؟) چون اینجوری جواب نداره.
سلام. حالت شروع این ماشین [tex]q_0[/tex] و حالت پایانی [tex]q_4[/tex] هست. Z رو هم انتهای پشته درنظر گرفتم. پرانتز سمت چپ رشته ورودی و حرف بالای پشته و پرانتز سمت راست حرفیه که وارد پشته میشه:
[tex]q_0(b,Z)\to q_0(bZ)[/tex]
[tex]q_0(b,b)\to q_0(bb)[/tex]
[tex]q_0(a,Z)\to q_1(aaaZ)[/tex]
[tex]q_0(a,b)\to q_6(\lambda)[/tex]
[tex]q_6(\lambda,b)\to q_7(\lambda)[/tex]
[tex]q_7(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_6(\lambda,Z)\to q_1(aaZ)[/tex]
[tex]q_7(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_1(a,Z)\to q_1(aaaZ)[/tex]
[tex]q_1(a,Z)\to q_1(aaZ)[/tex]
[tex]q_1(a,a)\to q_1(aaaa)[/tex]
[tex]q_1(a,a)\to q_1(aaa)[/tex]
[tex]q_1(b,Z)\to q_1(bZ)[/tex]
[tex]q_1(b,b)\to q_1(bb)[/tex]
[tex]q_1(b,a)\to q_1(\lambda)[/tex]
[tex]q_1(a,b)\to q_2(\lambda)[/tex]
[tex]q_2(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_2(\lambda,b)\to q_3(\lambda)[/tex]
[tex]q_3(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_2(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_2(\lambda,Z)\to q_1(aaZ)[/tex]
[tex]q_3(\lambda,Z)\to q_1(Z)[/tex]
[tex]q_3(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_1(a,a)\to q_4(aaa)[/tex]
[tex]q_1(a,Z)\to q_4(aaZ)[/tex]
[tex]q_1(a,b)\to q_5(\lambda)[/tex]
[tex]q_1(\lambda,b)\to q_4(\lambda)[/tex]
[tex]q_1(\lambda,a)\to q_4(aa)[/tex]
[tex]q_4(b,a)\to q_4(\lambda)[/tex]
[tex]q_0(b,b)\to q_0(bb)[/tex]
[tex]q_0(a,Z)\to q_1(aaaZ)[/tex]
[tex]q_0(a,b)\to q_6(\lambda)[/tex]
[tex]q_6(\lambda,b)\to q_7(\lambda)[/tex]
[tex]q_7(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_6(\lambda,Z)\to q_1(aaZ)[/tex]
[tex]q_7(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_1(a,Z)\to q_1(aaaZ)[/tex]
[tex]q_1(a,Z)\to q_1(aaZ)[/tex]
[tex]q_1(a,a)\to q_1(aaaa)[/tex]
[tex]q_1(a,a)\to q_1(aaa)[/tex]
[tex]q_1(b,Z)\to q_1(bZ)[/tex]
[tex]q_1(b,b)\to q_1(bb)[/tex]
[tex]q_1(b,a)\to q_1(\lambda)[/tex]
[tex]q_1(a,b)\to q_2(\lambda)[/tex]
[tex]q_2(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_2(\lambda,b)\to q_3(\lambda)[/tex]
[tex]q_3(\lambda,b)\to q_1(\lambda)[/tex]
[tex]q_2(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_2(\lambda,Z)\to q_1(aaZ)[/tex]
[tex]q_3(\lambda,Z)\to q_1(Z)[/tex]
[tex]q_3(\lambda,Z)\to q_1(aZ)[/tex]
[tex]q_1(a,a)\to q_4(aaa)[/tex]
[tex]q_1(a,Z)\to q_4(aaZ)[/tex]
[tex]q_1(a,b)\to q_5(\lambda)[/tex]
[tex]q_1(\lambda,b)\to q_4(\lambda)[/tex]
[tex]q_1(\lambda,a)\to q_4(aa)[/tex]
[tex]q_4(b,a)\to q_4(\lambda)[/tex]
[tex]q_4(\lambda,a)\to q_8(a)[/tex]
[tex]q_4(\lambda,b)\to q_8(b)[/tex]
[tex]q_4(\lambda,b)\to q_8(b)[/tex]
توضیحش خیلی زیاده. مشخصه که رشته های پذیرفته حداقل ۲تا a دارن که توی شرط صدق بکنن. ار [tex]q_0[/tex] به [tex]q_1[/tex] به ازای یک a سه تا a توی پشته میریزه (یا به همین نسبت b خط میزنه) و از [tex]q_1[/tex] به [tex]q_4[/tex] به ازای یک a دوتا a توی پشته میریزه (یا b خط میزنه). توی حلقه هم ۲ یا ۳تا اضافه میکنه. سوال سختی بود و پیاده سازیش مشکل بود. حالت [tex]q_8[/tex] هم برای وقتیه که با تمام شدن رشته، پشته خالی نشده باشه.
اوفف چقدر زیاد!!
من مساوی هاشو اشتباهی نذاشتم
اگه برای یه مثال ساده تر مثلا na(x) < nb(x) < 2na(x)
یه توضیحی میدادید خیلی خوب می شد برم ببینم اینو می فهمم یا نه!!
Lakikharin عزیز خیلی ممنونم ازت که وقت گذاشتی
موفق باشی
اگه مساوی داشت خیلی ساده تر بود. اگه قراره مساوی نداشته باشه باید حداقل یکبار به ازای یک b سه تا a و یکبار هم برای یک b دوتا a خط بزنیم.
الگوریتممو توضیح میدم:
۱- هر تعداد b در ابتدا میگیره توی پشته پوش میکنه.
۲- اولین a رو که گرفت شرط های زیر رو چک میکنه و بعد به حالت بعدی میره:
الف: اگه توی پشته Z بود، سه تا a به پشته اضافه میکنه.
ب: اگه توی پشته b بود، درصورتی که تعداد b های پشته حداقل سه تا بود، سه تا از b هارو خط میزنه. اگرم کمتر از سه تا بود، b هارو خط زده و به اندازه اختلاف b ها تا سه، a به پشته اضافه میکنه. مثلاً اگه یه b داشتیم، اونو خط میزنه و دوتا a به پشته اضافه میکنه.
۳- هر تعداد b که دید یا از پشته a خط میزنه و یا یه b به پشته اضافه میکنه که حذف یا اضافه کردن a یا b به پشته بستگی داره. اگه a دید هم یا دو یا سه تا a اضافه میکنه و یا دو یا سه تا b خط میزنه.(شرط خط زدن درصورتی که تعداد b کافی نبود مشابه حالت "ب" میشه. یعنی a اضافه میکنه.) حالا که نگاه میکنم بعضی از حالات ماشین اصلاً اتفاق نمی افته. ولی توی رشته ها تاثیر نداره. اضافی هارو پاک کردم. (شرط اینکه توی پشتمون a و b رو بطور همزمان نداریم رو درنظر نگرفته بودم.)
۴- آخرین a رو گرفته و با چک کردن محتوای پشته، یا دوتا b خط میزنه و یا یه b خط میزنه و یه a اضافه میکنه و یا دوتا a اضافه میکنه.
۵- در آخر هم به ازای b های باقی مونده a هارو خط میزنه. و اگه رشته تموم شد و پشتمون خالی نبود به حالت تله میره.
چون ماشینمون نامعینه، رشته های درست رو در حالتی که با آخرین a به حالت پایانی بره و با b های باقیمونه توی حالت پایانی بمونه رو قبول میکنه.
اگه سوال دومتون (مثال ساده تر مثلا na(x) < nb(x) < 2na(x) )مساوی داشته باشه ساده تره. باید به ازای هر b یا یک و یا دو a خط بزنیم. گرامرش میشه:
[tex]S\to SS|aSb|bSa|aSaSb|aSbSa|bSaSa|\lambda[/tex]
تبدیل گرامر به ماشین پشته ای هم سادست. اول یه S توی پشته پوش میکنیم و از q0 به q1 میریم و روی یک حلقه از q1 به خودش تمام قوانین گرامرو مینویسیم و با نال درصورت خالی بودن پشته به حالت پایانی میریم.
سلام دوستان
سوال ۴ قسمت h فصل ۷ بخش ۱ تمرینات لینز آیا ماشینش رو درست رسم کرده؟ هر رشته ای رو مثال می زنم پذیرفته نمی شه؟
سوال اینه ماشین npdaبرای زبان روبه رو بنویسید[tex]L={w:n_{a}(w)=2n_{b}(w)}[/tex]
تصویر ماشینش رو هم ضمیمه می کنم
[attachment=6068]
سلام. منظورتون از [tex](q_0,b,0)\to(q_1,0)[/tex] چیه؟ ماشینتونو اصلاح میکنم. حالت های مرتبط با q1 رو حذف کنید و به این شکل بنویسید:
[tex](q_0,b,0)\to(q_1,\lambda)[/tex]
[tex](q_1,\lambda,0)\to(q_0,\lambda)[/tex]
[tex](q_1,\lambda,z)\to(q_0,1z)[/tex]
[tex](q_1,\lambda,1)\to(q_0,11)[/tex]
[tex](q_1,\lambda,0)\to(q_0,\lambda)[/tex]
[tex](q_1,\lambda,z)\to(q_0,1z)[/tex]
[tex](q_1,\lambda,1)\to(q_0,11)[/tex]
یعنی بجای یک b یا باید دوتا a خط بزنیم (دوتا صفر خط بزنیم) و یا یه a خط زده و یه b اضافه کنیم (یه صفر خط زده و یه ۱ اضافه کنیم) و یا دوتا b اضافه کنیم (دوتا ۱ اضافه کنیم). این حالات به دو سمبل بالایی پشته بستگی داره.
ماشینی که فرستادید صحیح هست و فکر نمیکنم نیازی به تصحیح داشته باشه.
q0 که نیاز به توضیح نداره.
اما از اونجا که مشکل داشتید توضیح میدم. وقتی b میاد و بالای پشته ۰ هست تغییر وضعیت میدیم و دوباره اون صفر رو میریزیم داخل پشته، اما این تغییر وضعیت مشخص میکنه که یکی از دو b مربوط به ۰ دریافت شده حالا اگر حرف بعدی b نباشد تمام a ها رو مثل همون وضعیت q0 دریافت میکنه و بعد با رسیدن به اولین b صفری که (حتما) بالای پشته هست رو بر میداره و تغییر وضعیت میده به همون q0 .
این دقیقا کاری بود که ماشین باید انجام میداد.
یک مثال :
رشته ababbb
(q0,ababbb,z) ->(q0,babbb,0z)->(q1,abbb,0z)-> (q1,bbb,00z)->(q0,bb,0z)->(q1,b,0z)->(q0,lambda,z)->(qf,lamda,z)
(۲۲ مرداد ۱۳۹۱ ۰۶:۵۰ ب.ظ)javadem نوشته شده توسط: یک مثال :
رشته ababbb
(q0,ababbb,z) ->(q0,babbb,0z)->(q1,abbb,0z)-> (q1,bbb,00z)->(q0,bb,0z)->(q1,b,0z)->(q0,lambda,z)->(qf,lamda,z)
ببخشید ولی این رشته ۲ تا a و ۴ تا b داره. این رشته جزء زبان نیست. این ماشین baa رو هم قبول میکنه (که جزء زبانه و میتونم بگم جای a و b عوض نشده). همینطور baaabb رو.
اوه بله کاملا صحیح میفرمایید.
عذر میخوام.
سلام ممنون از دوستانی که پاسخ دادند، من هنوز مشکل دارم، اما آیا قبول دارید که ماشینش مشکل داره؟
بعد یه سوال دیگه ، آیا امکان داره وقتی مثلا رشته ی abbaaa رو داریم بعد از اینکه a میاد خوب ۰ می ره تو پشته،b که میاد ۰ برداشته می شه و جاش لامبدا گذاشته می شه حالا ما تو q1 هستیم و می خواد b دوم بیاد اما حالتی نداریم که با آمدن b بالای پشته z باشه، در این حالت آیا مجازیم از حالت (lambda,z/1z) برای رفتن به q0 استفاده کنیم و بعد کار را با q0 ادامه دهیم؟
(در مثال و سوال این پستم پیگیری حالت ها رو براساس تغییراتی که جناب جویباری فرموده بودند بیان کردم)
(۲۴ مرداد ۱۳۹۱ ۰۹:۰۵ ق.ظ)fa_karoon نوشته شده توسط: سلام ممنون از دوستانی که پاسخ دادند، من هنوز مشکل دارم، اما آیا قبول دارید که ماشینش مشکل داره؟
بعد یه سوال دیگه ، آیا امکان داره وقتی مثلا رشته ی abbaaa رو داریم بعد از اینکه a میاد خوب ۰ می ره تو پشته،b که میاد ۰ برداشته می شه و جاش لامبدا گذاشته می شه حالا ما تو q1 هستیم و می خواد b دوم بیاد اما حالتی نداریم که با آمدن b بالای پشته z باشه، در این حالت آیا مجازیم از حالت (lambda,z/1z) برای رفتن به q0 استفاده کنیم و بعد کار را با q0 ادامه دهیم؟
(در مثال و سوال این پستم پیگیری حالت ها رو براساس تغییراتی که جناب جویباری فرموده بودند بیان کردم)
درسته. بعد یک b میگیریم و پشتمون میشه ۱۱۱ و با گرفتن سه تا a پشتمون خالی میشه و به حالت پایانی میریم.