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

چرا این زبان قطعی است؟ 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 میکنیم اگه تو انتها که رشته تموم شد پشته خالی بود رشته پذیرفته میشه و در غیر این صورت پذیرفته نمیشه.میبینید که عدم قطعیت تو ماشینمون نداشتیم
ببخشید اگه بد توضیح دادم



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  ios 15.1 (4) M Router 2911 Cisco rh1995 ۰ ۹۰۳ ۰۴ دى ۱۴۰۰ ۰۸:۱۷ ب.ظ
آخرین ارسال: rh1995
  کمک در باره این تروجان Ghasemiyeh ۲ ۲,۶۲۰ ۲۵ آذر ۱۴۰۰ ۰۳:۰۰ ق.ظ
آخرین ارسال: one hacker alone
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۴۳۶ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  تفاوت classification algorithm و regression algorithm چیه؟ sajadg ۶ ۹,۰۸۱ ۱۵ خرداد ۱۴۰۰ ۰۱:۴۳ ب.ظ
آخرین ارسال: cyruskingsolomon
Heart هزینه عشق واقعی چقدر است aatwo ۵ ۵,۳۰۸ ۱۳ بهمن ۱۳۹۹ ۱۰:۱۴ ب.ظ
آخرین ارسال: ghaderZ
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۲,۵۹۴ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  چجوری بفهمیم سرور hp اورجینال است یا خیر!؟ azade1992 ۱ ۲,۲۱۶ ۰۳ مهر ۱۳۹۹ ۱۰:۵۹ ق.ظ
آخرین ارسال: diiyan
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۲,۷۳۴ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo
  همکار در حوزه speech recognition و برنامه نویسی اندروید pasargad7788 ۰ ۱,۹۵۰ ۳۱ خرداد ۱۳۹۹ ۰۹:۰۶ ب.ظ
آخرین ارسال: pasargad7788
  چرا یادگیری برنامه نویسی ؟ elecomco ۰ ۲,۲۳۵ ۰۲ خرداد ۱۳۹۹ ۰۲:۵۷ ب.ظ
آخرین ارسال: elecomco

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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