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

چرا این زبان قطعی است؟ ww^R

ارسال:
  

archer22 پرسیده:

چرا این زبان قطعی است؟ ww^R

۱/چرا زبان [tex]L=\{ww^R:w\in L(b^{\ast}a^ )\}[/tex] قطعی است؟
(در صورتی که میدونیم [tex]L=\{ww^R:w\in(b^{ } a^{ })^{\ast}\}[/tex] قطعی نیستش.)

۴
ارسال:
  

MiladCr7 پاسخ داده:

RE: چرا این زبان قطعی است؟

سلام ببینید میتونیم اینجوری کار کنیم که ایتدا هر چی b دیدیم تو پشته Push کنیم تا اینکه به a برسیم.از اونجایی که توی این زبان که نوشتید تعداد a ها باید حتما زوج باشه.پس به ازای هر a از رشته w یه a ی متناظر توی [tex]w^R[/tex] هم داریم.
خب پس الان بالای پشته b هستش و a میبینیم،اون a رو Push میکنیم و حالا اگه دوباره a اومد میگیم این a همون a متناظر با قبلی هستش پس a رو از بالای پشته Pop میکنیم حالا اگه دوباره a بیاد چون بالای پشته b هستش میدونیم این a مربوط به w هستش و Push میکنیم حالا بالای پشته a هستش و اگه دوباره a بیاد میدونیم باید همون a متناظر باشه پس Pop میکنیم.اینقد این کارا انجام میدیم تا b بیاد.اگه وقتی b اومد بالای پشته a بودش که غیرقابل قبول هست اون رشته چون میدونیم تعداد a ها فرد بوده(که برای [tex]ww^R[/tex] این اشتباهه) و اگه
بالای پشته b بود یعنی تعداد a ها درست بوده و با هم مطابقت داشتند.حالا به ازای هر b که میبینیم یه b از بالای پشته Pop میکنیم اگه تو انتها که رشته تموم شد پشته خالی بود رشته پذیرفته میشه و در غیر این صورت پذیرفته نمیشه.میبینید که عدم قطعیت تو ماشینمون نداشتیم
ببخشید اگه بد توضیح دادم



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۳,۴۷۹ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۴,۰۰۲ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۲,۴۰۰ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۵۶۶ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۹۹۳ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۸۶۱ ۰۷ بهمن ۱۳۹۳ ۰۹:۰۲ ب.ظ
آخرین ارسال: Hamid_0311
  مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی mostafa2012 ۴ ۲,۳۴۷ ۰۶ بهمن ۱۳۹۳ ۰۲:۳۲ ب.ظ
آخرین ارسال: mostafa2012
  تشخیص مستقل از متن و قطعی بودن چند زبان mostafa2012 ۱۱ ۵,۹۳۸ ۰۵ بهمن ۱۳۹۳ ۰۶:۲۲ ب.ظ
آخرین ارسال: Hamid_0311
Question چرا این زبان حساس به متن است؟ Ametrine ۲ ۸۰۱ ۲۹ دى ۱۳۹۳ ۱۰:۰۲ ب.ظ
آخرین ارسال: Ametrine
  تشخیص مستقل از متن قطعی و عیر قطعی بودن ۶ زبان maryam.roshan ۴ ۱,۵۵۹ ۲۹ دى ۱۳۹۳ ۰۴:۳۵ ب.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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