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

چرا این زبان قطعی است؟ 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