سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند - نسخه‌ی قابل چاپ

سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند - be_sooye_movafaghiat - 01 خرداد ۱۳۹۳ ۰۸:۵۴ ب.ظ دوستان من در مورد نوع زبان هایی که در اون رشته w با رشته معکوسش یعنی w^R هست مشکل دارم یه مقداری... می تونم خواهش کنم ازتون که در مورد تعیین نوع این ۶ موردی که w و w^R با هم وجود دارن، کمکم کنین؟ خیلی احتیاج دارم.. اینکه کدومشون مستقل از متن هستن و کدومشون منظم؟ ممنونم پیشاپیش ازتون... ۱- {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}

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند - Jooybari - 02 خرداد ۱۳۹۳ ۱۲:۰۸ ق.ظ سلام. ۱- منظم. ۲- مستقل از متن. ۳- مستقل از متن. c یک حرفه نه رشته ای از a,b. ۴- باید L1 و L2 رو تعریف کنید. اگه منظور از این زبانها همون زبانهای ۱ و ۲ باشه منظم میشه. ۵- مستقل از متن. ۶- حساس به متن.

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند - fatemeh69 - 02 خرداد ۱۳۹۳ ۰۱:۵۱ ق.ظ ۱- رشته ی 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.

RE: سوال در مورد تعیین منظم یا مستفل از متن بودن زبان هایی که توسط w و w^R تعریف می شوند - MShariati - 02 خرداد ۱۳۹۳ ۱۰:۳۶ ق.ظ سؤال اولی خیلی غلط اندازه... مشکل از اینجاست که ممکنه lambda رشته در نظر گرفته نشه، این هم منطقی و هم قریب به ذهنه، چرا که طولش صفره. اگه منظور شما رو بگیریم که v,w برابر *(a,b) باشن، حل دوستان درسته ولی اگه w برابر +(a,b) فرض بشه کار خیلی فرق می کنه: زبان اولی حتی مستقل از متن قطعی هم نمی شه! راهنمای شهودیش اینه که اولاً ماشین ما باید الگوی w رو (که نامتناهیه) به خاطر بسپره تا بتونه عکس اون رشته رو بررسی کنه و ثانیاً ماشین ما در هر لحظه نمیدونه که آیا w تمام شده (که شروع به بررسی عکس اون کنه) یا نه. در کل Expression چرتیه و فقط بدرد طراحان موذی کنکور می خوره!