۰
subtitle
ارسال: #۱
سوال از Npda
سلام کسی می تونه برای زبان زیر Npda رسم کنه؟تو تمرین ۴ بخش ۱ فصل ۷ ویرایش ۴ لینزه (صفحه ۱۷۲)
لطفا نگید از حل تمرینش ببین چون حلش رو ندارم فقط جواب سوال رو بگید.(با شکل)
لطفا نگید از حل تمرینش ببین چون حلش رو ندارم فقط جواب سوال رو بگید.(با شکل)
کد:
L = {w:2na(w)<nb(w)<3na(w)}
۰
ارسال: #۲
سوال از Npda
سلام. حالت شروع این ماشین [tex]q_0[/tex] و حالت پایانی [tex]q_4[/tex] هست. Z رو هم انتهای پشته درنظر گرفتم. پرانتز سمت چپ رشته ورودی و حرف بالای پشته و پرانتز سمت راست حرفیه که وارد پشته میشه:
توضیحش خیلی زیاده. مشخصه که رشته های پذیرفته حداقل ۲تا 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] هم برای وقتیه که با تمام شدن رشته، پشته خالی نشده باشه.
[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] هم برای وقتیه که با تمام شدن رشته، پشته خالی نشده باشه.
۰
ارسال: #۳
سوال از Npda
اگه مساوی داشت خیلی ساده تر بود. اگه قراره مساوی نداشته باشه باید حداقل یکبار به ازای یک 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 خط بزنیم. گرامرش میشه:
تبدیل گرامر به ماشین پشته ای هم سادست. اول یه S توی پشته پوش میکنیم و از q0 به q1 میریم و روی یک حلقه از q1 به خودش تمام قوانین گرامرو مینویسیم و با نال درصورت خالی بودن پشته به حالت پایانی میریم.
الگوریتممو توضیح میدم:
۱- هر تعداد 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 به خودش تمام قوانین گرامرو مینویسیم و با نال درصورت خالی بودن پشته به حالت پایانی میریم.
۰
۰
ارسال: #۵
سوال از Npda
اوفف چقدر زیاد!!
من مساوی هاشو اشتباهی نذاشتم
اگه برای یه مثال ساده تر مثلا na(x) < nb(x) < 2na(x)
یه توضیحی میدادید خیلی خوب می شد برم ببینم اینو می فهمم یا نه!!
Lakikharin عزیز خیلی ممنونم ازت که وقت گذاشتی
موفق باشی
من مساوی هاشو اشتباهی نذاشتم
اگه برای یه مثال ساده تر مثلا na(x) < nb(x) < 2na(x)
یه توضیحی میدادید خیلی خوب می شد برم ببینم اینو می فهمم یا نه!!
Lakikharin عزیز خیلی ممنونم ازت که وقت گذاشتی
موفق باشی
۰
ارسال: #۶
RE: سوال از Npda
سلام دوستان
سوال ۴ قسمت h فصل ۷ بخش ۱ تمرینات لینز آیا ماشینش رو درست رسم کرده؟ هر رشته ای رو مثال می زنم پذیرفته نمی شه؟
سوال اینه ماشین npdaبرای زبان روبه رو بنویسید[tex]L={w:n_{a}(w)=2n_{b}(w)}[/tex]
تصویر ماشینش رو هم ضمیمه می کنم
سوال ۴ قسمت h فصل ۷ بخش ۱ تمرینات لینز آیا ماشینش رو درست رسم کرده؟ هر رشته ای رو مثال می زنم پذیرفته نمی شه؟
سوال اینه ماشین npdaبرای زبان روبه رو بنویسید[tex]L={w:n_{a}(w)=2n_{b}(w)}[/tex]
تصویر ماشینش رو هم ضمیمه می کنم
۰
ارسال: #۷
سوال از Npda
سلام. منظورتون از [tex](q_0,b,0)\to(q_1,0)[/tex] چیه؟ ماشینتونو اصلاح میکنم. حالت های مرتبط با q1 رو حذف کنید و به این شکل بنویسید:
یعنی بجای یک b یا باید دوتا a خط بزنیم (دوتا صفر خط بزنیم) و یا یه a خط زده و یه b اضافه کنیم (یه صفر خط زده و یه ۱ اضافه کنیم) و یا دوتا b اضافه کنیم (دوتا ۱ اضافه کنیم). این حالات به دو سمبل بالایی پشته بستگی داره.
[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 اضافه کنیم (دوتا ۱ اضافه کنیم). این حالات به دو سمبل بالایی پشته بستگی داره.
۰
ارسال: #۸
RE: سوال از Npda
ماشینی که فرستادید صحیح هست و فکر نمیکنم نیازی به تصحیح داشته باشه.
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)
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)
ارسال: #۹
RE: سوال از Npda
(۲۲ مرداد ۱۳۹۱ ۰۶:۵۰ ب.ظ)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 رو.
۰
۰
ارسال: #۱۱
سوال از Npda
سلام ممنون از دوستانی که پاسخ دادند، من هنوز مشکل دارم، اما آیا قبول دارید که ماشینش مشکل داره؟
بعد یه سوال دیگه ، آیا امکان داره وقتی مثلا رشته ی abbaaa رو داریم بعد از اینکه a میاد خوب ۰ می ره تو پشته،b که میاد ۰ برداشته می شه و جاش لامبدا گذاشته می شه حالا ما تو q1 هستیم و می خواد b دوم بیاد اما حالتی نداریم که با آمدن b بالای پشته z باشه، در این حالت آیا مجازیم از حالت (lambda,z/1z) برای رفتن به q0 استفاده کنیم و بعد کار را با q0 ادامه دهیم؟
(در مثال و سوال این پستم پیگیری حالت ها رو براساس تغییراتی که جناب جویباری فرموده بودند بیان کردم)
بعد یه سوال دیگه ، آیا امکان داره وقتی مثلا رشته ی abbaaa رو داریم بعد از اینکه a میاد خوب ۰ می ره تو پشته،b که میاد ۰ برداشته می شه و جاش لامبدا گذاشته می شه حالا ما تو q1 هستیم و می خواد b دوم بیاد اما حالتی نداریم که با آمدن b بالای پشته z باشه، در این حالت آیا مجازیم از حالت (lambda,z/1z) برای رفتن به q0 استفاده کنیم و بعد کار را با q0 ادامه دهیم؟
(در مثال و سوال این پستم پیگیری حالت ها رو براساس تغییراتی که جناب جویباری فرموده بودند بیان کردم)
ارسال: #۱۲
RE: سوال از Npda
(۲۴ مرداد ۱۳۹۱ ۰۹:۰۵ ق.ظ)fa_karoon نوشته شده توسط: سلام ممنون از دوستانی که پاسخ دادند، من هنوز مشکل دارم، اما آیا قبول دارید که ماشینش مشکل داره؟
بعد یه سوال دیگه ، آیا امکان داره وقتی مثلا رشته ی abbaaa رو داریم بعد از اینکه a میاد خوب ۰ می ره تو پشته،b که میاد ۰ برداشته می شه و جاش لامبدا گذاشته می شه حالا ما تو q1 هستیم و می خواد b دوم بیاد اما حالتی نداریم که با آمدن b بالای پشته z باشه، در این حالت آیا مجازیم از حالت (lambda,z/1z) برای رفتن به q0 استفاده کنیم و بعد کار را با q0 ادامه دهیم؟
(در مثال و سوال این پستم پیگیری حالت ها رو براساس تغییراتی که جناب جویباری فرموده بودند بیان کردم)
درسته. بعد یک b میگیریم و پشتمون میشه ۱۱۱ و با گرفتن سه تا a پشتمون خالی میشه و به حالت پایانی میریم.
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| PDA and NPDA | gmh1993 | ۱ | ۱,۷۴۹ |
۱۱ خرداد ۱۳۹۳ ۰۷:۵۵ ب.ظ آخرین ارسال: aamitis |
|
| الگوریتم یافتن گرامر یک npda | پرهام | ۱ | ۳,۸۷۴ |
۱۷ مرداد ۱۳۹۰ ۰۱:۱۳ ق.ظ آخرین ارسال: ف.ش |
|
| npda در این گرامر | masoudkhan | ۳ | ۲,۱۵۰ |
۱۸ خرداد ۱۳۹۰ ۰۳:۲۵ ب.ظ آخرین ارسال: ف.ش |
|
| راه تستی برای شناسایی زبان dpda از npda چیست ؟ | bahar | ۱ | ۳,۴۰۵ |
۰۴ آذر ۱۳۸۹ ۰۸:۰۶ ب.ظ آخرین ارسال: sepid |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close