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

سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند

ارسال:
  

be_sooye_movafaghiat پرسیده:

سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند

دوستان من در مورد نوع زبان هایی که در اون رشته w با رشته معکوسش یعنی w^R هست مشکل دارم یه مقداری...
می تونم خواهش کنم ازتون که در مورد تعیین نوع این ۶ موردی که w و w^R با هم وجود دارن، کمکم کنین؟ خیلی احتیاج دارم..Undecided

اینکه کدومشون مستقل از متن هستن و کدومشون منظم؟

ممنونم پیشاپیش ازتون...


۱-
{ww^R v | v,w= (hameye reshteha ba a,b)}

۲-
{(w=w^R | w =(hame reshteha ba a,b)}

۳-
{wcw^R | w,c= hameye reshteha ba a,b}

۴-
ww^R | w ozve L1 , w^R ozve L2}

۵-
ww^R | w= hameye reshteha ba a,b}

۶-
{ww^R | w=w^R}

۲
ارسال:
  

fatemeh69 پاسخ داده:

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند

۱- رشته ی w می تواند [tex]\lambda[/tex]باشد پس هر رشته ای از [tex]Sigma^{\ast}[/tex]را می توان به فرم [tex]ww^Rv[/tex] نوشت
مثلا در رشته ی aababaabbbbb می توان گفت w و [tex]w^R[/tex] برابر با [tex]\lambda[/tex] هستند و همه ی رشته برابر با v است
پس همه ی رشته های [tex]Sigma^{\ast}[/tex] را می توان به این فرم نوشت پس زبان داده شده برابر با [tex]Sigma^{\ast}[/tex] است.
پس منظم است.

۲- در مورد این زبان باید چک کنیم ببینیم آیا w با [tex]w^R[/tex] برابر است یا نه. این زبان رشته های پالیندرام یا آیتنه ای را می پذیردرشته هایی که چه از چپ به راست خوانده شوند چه از راست به چپ به یک مدل خوانده می شوند.
برای چک کردن این که آیا [tex]w=w^R[/tex]هست یا نه باید از یک ماشین پشتهای کمک بگیریم ابتدا w را تا وسط در پشته پوش کنیم حالا چون سیستم پشته lifo است ما به آخرین کاراکتر قبل از نصف رشته دسترسی داریم حالا یکی یکی عناصر بالای پشته را با عناصر نیمه ی دوم مقایسه می کنیم. پس مستقل از متن است.
۳- مانند بالایی عمل می کنیم فقط این بار رشته را تا وقتی که به c برسیم push می کنیم پس اینم مستقل از متنه
۴- باید دید منظور از L1و L2 چیه . در تایید جواب جناب جویباری بگم اگه منظور همین ۱و ۲ است چون مجددا می شه w و [tex]w^R[/tex] از قسمت L1 را برابر با [tex]\lambda[/tex] در نظر گرفت و همین طور w ای که از L2 میاد را هم میشه [tex]\lambda[/tex] در نظر گرفت پس کل رشته برابر می شه با همون v پس مجددا این زبان برابر است با [tex]Sigma^{\ast}[/tex] پس منظم است.
۵- مستقل از متن مانند استدلال زبان دوم
۶- منظور زبان این است که رشته ها به فرم ww هستند که می دانیم از نوع حساس به متن است چون نمی توان برای آن ماشین پشته ای طراحی کرد چون اگر w اول را داخل پشته push کنیم الان متا به خاظر سیستم lifo ی پشته به [tex]w^R[/tex] دسترسی دارینم نه w.

۲
ارسال:
  

Jooybari پاسخ داده:

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند

سلام.

۱- منظم.

۲- مستقل از متن.

۳- مستقل از متن. c یک حرفه نه رشته ای از a,b.

۴- باید L1 و L2 رو تعریف کنید. اگه منظور از این زبانها همون زبانهای ۱ و ۲ باشه منظم میشه.

۵- مستقل از متن.

۶- حساس به متن.

۰
ارسال:
  

MShariati پاسخ داده:

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند

سؤال اولی خیلی غلط اندازه...
مشکل از اینجاست که ممکنه lambda رشته در نظر گرفته نشه، این هم منطقی و هم قریب به ذهنه، چرا که طولش صفره.

اگه منظور شما رو بگیریم که v,w برابر *(a,b) باشن، حل دوستان درسته ولی اگه w برابر +(a,b) فرض بشه کار خیلی فرق می کنه:
زبان اولی حتی مستقل از متن قطعی هم نمی شه! راهنمای شهودیش اینه که اولاً ماشین ما باید الگوی w رو (که نامتناهیه) به خاطر بسپره تا بتونه عکس اون رشته رو بررسی کنه و ثانیاً ماشین ما در هر لحظه نمیدونه که آیا w تمام شده (که شروع به بررسی عکس اون کنه) یا نه.

در کل Expression چرتیه و فقط بدرد طراحان موذی کنکور می خوره!



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعریف ای پی استاتیک در ویندوز ۱۱ و مودم و دستگاه تردد babmelo ۰ ۵۰۸ ۰۳ تیر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: babmelo
  راهنمایی در مورد تعریف محیط عملیاتی داروخانه برای آز پایگاه داده ngmsshd ۲ ۷,۶۰۸ ۰۴ اردیبهشت ۱۴۰۲ ۰۵:۲۹ ب.ظ
آخرین ارسال: Eris_mw
  سوال در مورد صفحه بندی در سیستم عامل Azadam ۱ ۱,۵۹۱ ۱۳ دى ۱۴۰۰ ۱۱:۰۴ ق.ظ
آخرین ارسال: Azadam
Music معرفی آهنگ‌هایی که حسابی دوسشون داریم! Amir V ۱,۱۵۱ ۲۴۱,۸۲۹ ۳۰ آذر ۱۴۰۰ ۰۵:۴۹ ب.ظ
آخرین ارسال: Azaadi
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۵۶۵ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۹۹ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۱,۳۶۲ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  سوال در مورد سهمیه رتبه اولی rezamim2020 ۰ ۲,۰۰۸ ۱۶ شهریور ۱۳۹۹ ۰۴:۳۵ ب.ظ
آخرین ارسال: rezamim2020
  اثبات بومی بودن sirvan.t ۸ ۵,۳۲۳ ۱۰ اسفند ۱۳۹۸ ۰۹:۴۶ ب.ظ
آخرین ارسال: WILL
  درآمد شما در سایت هایی مثل کافه بازار و مایکت چقدر است؟ applepeach ۴ ۷,۶۲۴ ۲۵ دى ۱۳۹۸ ۱۱:۲۵ ق.ظ
آخرین ارسال: packationmachinery

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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