زمان کنونی: ۰۵ مهر ۱۳۹۹, ۰۷:۴۲ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سال ۷۷ اشکال در مستقل از متن

ارسال:
  

popp پرسیده:

سال ۷۷ اشکال در مستقل از متن

سلام
این زبان در تست ساله ۷۷ اومده ظاهرا مستقل از متن هست.
میشه یکی از دوستان توضیح بده اینو چطور میشه با پشته پذیرش کرد؟
ممنون میشم


[tex]l1={a^{p}b^{q}a^{p}b^{s}}|p,q,s\geq 0}[/tex]

۱
ارسال:
  

انرژی مثبت پاسخ داده:

اشکال در مستقل از متن در تست سال ۷۷

ببینید از اون جایی که توانهای b و a بهم ربطی ندارن یعنی رابطه ای بین اونا برقرار نیست با پشته قابل پیاده سازیه شما بعد از این که pتا a رو روی پشته قرار دادید به نظرم لازم نیست b‌ها رو روی پشته بذارید چک می کنید زمانی که دوباره به a رسیدید به ازا هر a یک a ازبالای پشته برمیدارید . بعد هم می تونید هر تعدادb داشته بتشید.

اگه اشتباه بود دوستان اصلاح کنند

۱
ارسال:
  

reyhaneh64 پاسخ داده:

RE: اشکال در مستقل از متن در تست سال ۷۷

ابتدای کار اگر a اومد‌، آن را درپشته پوش میکنیم،اگر b اومد دو حالت داره: ممکنه این b‌، اولین حرف رشته باشه، که به هر تعدادی که نیازه از ورودی میپذیره،(و میتوان b^q و b^s رو باهم در نظر گرفت) اما تو پشته تغییری نمیدیم،اگر به پایان رشته رسیدیم و تو استک چیزی نبود رشته پذیرفته میشه، اما اگر b بعد از a اومده باشه،به هر تعداد که بیاد از ورودی میگیریم و در پشته تغییری نمیدیم، تنها فرقش با حالت قبل اینه که ممکنه‌، بعد از a‌، b ببینه،که در این صورت تا جایی که در پشته a هست و a میاد از پشته پاپ میکنیم،اگر پشته خالی شد، و رشته تموم شد که پذیرفته میشه، اما بعد اگر b اومد و پشته خالی بود که میپذیره و تو استک چیزی نمیریزه‌، تا به پایان رشته برسیم .
هر رشته ای که جز زبان باشه میتونیم با این ساختار پیادش کنیم.

۰
ارسال:
  

mfXpert پاسخ داده:

RE: اشکال در مستقل از متن در تست سال ۷۷

کافیه این زبان رو به صورت الحاق دو زبان زیر در نظر بگیرید:
[tex]L=\{a^{p}b^{q}a^{p}\}.\{b^{s}\}[/tex]
خیلی بدیهیه که میشه برای چنین زبانی یک ماشین پشته ای طراحی کرد

۰
ارسال:
  

popp پاسخ داده:

اشکال در مستقل از متن در تست سال ۷۷

چطور میشه از رو پشته p تا a گذاشت(یا برداشت) در صورتی که بالای پشته ما ابتدا q تا b داریم؟ به تعداد p دسترسی نداریم که!!!

۰
ارسال:
  

popp پاسخ داده:

اشکال در مستقل از متن در تست سال ۷۷

نمیدونم فهمیدم یا نه!!!
یعنی منظورتون این شد که اگه بعده b، a اومد b رو تو پشته وارد نمیکنیم!! آره؟ مگه نباید هرچی اومد باید با پشته پردازش بشه؟
ممنون از وقتی که گذاشتین!!

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: اشکال در مستقل از متن در تست سال ۷۷

حتما نباید در پشته چیزی اضافه بشه، میتونیم تو حرکتمون به جاش لاندا بذاریم که چیزی توش اضافه نمیشه.
مثلا اگر یه ماشین dfa رو بخواهیم با npda پیاده سازی کنیم، مثل حالتی که فرضا میخواستیم ماشین حاصل از اشتراک یک زبان منظم(dfa) و زبان مستقل از متن(npda) رو تولید کنیم،برای اثبات مستقل از متن بودن زبان حاصل میگفتیم dfa رو میشه با ساختار پشته پیاده سازی کرد اما بدون اینکه چیزی تو پشته اضافه بشه....
اگه ابهامی بود بفرمایید که توضیح بیشتر بدم.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۷,۸۰۶ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  معرفی سایت برای شروع یک کسب وکار مستقل sadrasamina ۰ ۷ ۰۹ مرداد ۱۳۹۹ ۱۱:۲۸ ق.ظ
آخرین ارسال: sadrasamina
  رفع اشکال نصب جاوا، مشکل ساخته نشدن virtual machine shiivaa ۱۱ ۹,۳۱۴ ۲۷ فروردین ۱۳۹۹ ۱۲:۴۷ ق.ظ
آخرین ارسال: jaafarzahravi
  رفع اشکال سؤالات کنکور دکتری هوش مصنوعی Lootus ۱۲ ۱,۳۹۳ ۲۵ اسفند ۱۳۹۸ ۰۷:۳۹ ب.ظ
آخرین ارسال: Lootus
Question یک اشکال ریز، کمک لطفا! marvelous ۶ ۹۱۱ ۳۰ دى ۱۳۹۸ ۰۲:۱۶ ب.ظ
آخرین ارسال: marvelous
  گرامر مستقل از متن Sanazzz ۴ ۱,۴۸۴ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۸۹۱ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  رفع اشکال آزمون های استخامی nima88 ۴ ۱,۲۵۰ ۲۲ خرداد ۱۳۹۷ ۰۱:۱۴ ق.ظ
آخرین ارسال: ^_^
  متن کاوی zorro ۰ ۶۷۳ ۲۸ بهمن ۱۳۹۶ ۰۷:۲۸ ب.ظ
آخرین ارسال: zorro
  منظور این متن در آمار چیست؟ H-Arshad ۰ ۴۸۵ ۲۶ مهر ۱۳۹۶ ۰۳:۲۶ ق.ظ
آخرین ارسال: H-Arshad

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close