این زبان آیا مستقل از متنه ؟
منظم چه طور ؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۶ بهمن ۱۳۹۲ ۰۴:۴۸ ب.ظ)masoud67 نوشته شده توسط: این زبان آیا مستقل از متنه ؟
منظم چه طور ؟
والا تا اونجایی که مغز من جواب میده این منظمه چون میتونیم به ازای هر رشته ای از زبان w1 رو برابر لامبدا و سایر رشته رو به عنوان w2 بگیریم
البته اگه سوال رو درست متوجه شده باشم
(۱۶ بهمن ۱۳۹۲ ۰۴:۴۸ ب.ظ)masoud67 نوشته شده توسط: این زبان آیا مستقل از متنه ؟
منظم چه طور ؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
به نظر من منظمه(پس مستقل از متن هم هست) . همواره w1 را لاندا در نظر میگیریم و اون موقع زبان می شود سیگمااستار.
پ ن: البته من اون علامت زیرمجموعه رو اینطوری در نظر گرفتم که رشته w1 میتونه قسمتی از رشته w2 باشد.
سلام
این یکی از زبان های معروفی است که نه منظمه نه مستقل از متن
در واقع برای اینکه ببینیم یک رشته زیررشته زبان دیگری است باید حالات برابری دو رشته را بررسی کنیم که حالت تساوی هم در زبانهای مستقل از متن امکان ندارد یعنی پشته در جواب دادن به این سوال عاجز است!در واقع حتی با مستقل از متن غیر قطعی هم چنین امکانی وجود نداره چون ما نمی دانیم از کی رشته اول تموم شده که بعد به سراغ زیر مجموعه بودن اون نسبت به رشته دیگری بگردیم!اصلا حالت برابری در پشته امکان ندارد.پشته یکی می تواند تعداد رو بشمارد یکی هم reverse بودن رو....
ولی اگر مثل یکی از تستهای نظریه ۹۲ سوال ۵۶ زبان L3 گفته بود y زیر رشته ای از x است اون وقت مثلا می توانستیم به طور مثال y رو لاندا و x رو زیگما استار بگیریم که اون وقت کل زبان زیگما استار می شد و منظم بود و مستقل از متن هم بنابراین بود!در این سوال چون y رو محدود کرده و گفته یه زیررشته مثلا می توانیم لاندا رو بگیریم که اونوقت زیر مجموعه همه رشته ها است!ودر مجموعه ما هم صدق می کند.
ضمنا این چیزی که گفتم طبق pdf است که از پارسه دارم....که صراحتا این زبانو غیر منظم و غیر مستقل از متن اعلام کرده!
موفق باشید....
اول
به من بگو چطور یک کلمه زیر مجموعه یک کلمه دیگه میشه؟
(۱۶ بهمن ۱۳۹۲ ۰۵:۰۷ ب.ظ)mahsalove نوشته شده توسط: در واقع برای اینکه ببینیم یک رشته زیررشته زبان دیگری است باید حالات برابری دو رشته را بررسی کنیم که حالت تساوی هم در زبانهای مستقل از متن امکان ندارد یعنی پشته در جواب دادن به این سوال عاجز است!در واقع حتی با مستقل از متن غیر قطعی هم چنین امکانی وجود نداره چون ما نمی دانیم از کی رشته اول تموم شده که بعد به سراغ زیر مجموعه بودن اون نسبت به رشته دیگری بگردیم!اصلا حالت برابری در پشته امکان ندارد.پشته یکی می تواند تعداد رو بشمارد یکی هم reverse بودن رو....
سلام
اینجا گفته w1 و w2 عضو [tex]\{a,b\}^{*}[/tex] خب با این اوصاف این دو تا منظمن و تساویشون هم تصمیم پذیره. من متوجه نمیشیم شما چرا مستقل از متن فرضشون کردی؟
اینجا رشته رو نمی خوایم چک کنیم می خوایم ببینیم یک رشته زیر مجموعه ی رشته ی دیگه هست یا نه قائدتا این منظم یا مستقل از متن نیست چون باید ورودی داشته باشیم یا اینکه دو رشته در جایی ذخیره باشند مثلا روی یک نوار!
ببخشیدا
خوب برای اینکه بفهمیم یک رشته زیر مجموعه یک رشته دیگه هست آپولو که هوا نمی کنیم بفهمیم هست یا نه!
باید ببینیم آیا رشته دیگه الفبای مساوی با رشته اول دارد یا نه حالا همشو نخواهیم چک کنیم ولی باید تک تک الفبا ها رو تا جایی که ببینیم یکی زیر رشته دیگری هست یا نه چک کنیم یا به مثال نقض می رسیم و توقف می کنیم و یکی زیر رشته دیگری نیست!یا رشته که می خواهیم ببینیم زیر مجموعه دیگری است تمام می شود و متوجه می شویم زیر رشته دیگری است چ.ن مثال نقض پیدا نشد یا اصلا خود رشته است که باز هم برابری رو حتما تو این یه مورد باید چک کنیم!
اگر لاندا هم باشه که مثال نقض نیست چون زیرمجوعه دیگری حتما هست!وگرنه پشته که خودش حافظست و برای ذخیره شدن می توانیم ازش استفاده کنیم
شاید منظورتون اینه که نمی توانیم با پشته ای که خاصیت LIFO داره از ابتدای رشته یعنی برعکس رشته بشینیم چک کنیم که زیرمجموعه هست یا نه و نیاز به حافظه نامحدودتری به نام LBA هست!
موفق باشید.....
تا اونجایی که من متوجه شدم منظور آقا Riemann اینه که یه رشته نمیتونه زیر مجموعه رشته دیگه باشه. زیر مجموعه بودن در مورد زبان ها مطرح میشه
(۱۶ بهمن ۱۳۹۲ ۰۵:۲۸ ب.ظ)hosshah نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۵:۰۷ ب.ظ)mahsalove نوشته شده توسط: در واقع برای اینکه ببینیم یک رشته زیررشته زبان دیگری است باید حالات برابری دو رشته را بررسی کنیم که حالت تساوی هم در زبانهای مستقل از متن امکان ندارد یعنی پشته در جواب دادن به این سوال عاجز است!در واقع حتی با مستقل از متن غیر قطعی هم چنین امکانی وجود نداره چون ما نمی دانیم از کی رشته اول تموم شده که بعد به سراغ زیر مجموعه بودن اون نسبت به رشته دیگری بگردیم!اصلا حالت برابری در پشته امکان ندارد.پشته یکی می تواند تعداد رو بشمارد یکی هم reverse بودن رو....
سلام
اینجا گفته w1 و w2 عضو [tex]\{a,b\}^{*}[/tex] خب با این اوصاف این دو تا منظمن و تساویشون هم تصمیم پذیره. من متوجه نمیشیم شما چرا مستقل از متن فرضشون کردی؟
آخر این صفحه گفتم چرا مساوی بودن رو باید چک کنیم !و توسط حافظه مستقل از متن نمی توان این مساوی بودن رو چک کرد!ولی یه سوال کی گفته مساوی بودن دو مجموعه منظم تصمیم پذیر است؟!:/مساوی بودنی که مستقل از متن نمی تونه انجام بده منظم که محدودتره می تونه انجام بده!مساوی بودن جز مسائل تصمیم ناپذیره مستقل از متنه!:/
تشکر از همه
بعضی ها گفتند رشته اول را لاندا بگیریم نمیشه . چون گفته زیر مجموعه سره یا محض . پس اگر زبانمون مثلا لاندا خالی باشه و W1 برابر با لاندا در نظر بگیریم اونوقت دیگه w2 را نمیشه هیچی گرفت . پس این مورد اشتباهه واسه این زبان
مسئله بعدی اینه که واقعا علامت زیرمجموعه اینجا یعنی چه؟؟ که اگر زیر رشته بودن منظور باشه که مسلما مستقل نیست و همونطور که دوستان گفتند نیاز به حافظه و نوار هست. پس نتیجه میگیرم که این زبان مستقل نیست
(۱۶ بهمن ۱۳۹۲ ۰۶:۲۶ ب.ظ)mahsalove نوشته شده توسط: آخر این صفحه گفتم چرا مساوی بودن رو باید چک کنیم !و توسط حافظه مستقل از متن نمی توان این مساوی بودن رو چک کرد!ولی یه سوال کی گفته مساوی بودن دو مجموعه منظم تصمیم پذیر است؟!:/مساوی بودنی که مستقل از متن نمی تونه انجام بده منظم که محدودتره می تونه انجام بده!مساوی بودن جز مسائل تصمیم ناپذیره مستقل از متنه!:/
در مورد این زبان که مثل اینکه اصلا من متوجه نشده بودم و بله منظم و مستقل ازمتن نیست. اما وقتی میگم تساوی دو زبان منظم تصمیم پذیره یعنی میتونیم yes یا no بدیم
الگوریتم تساوی دو زبان مستقل ازمتن هم میتونه محاسبه تفاضل متقارن باشه. اگر حاصل تفاضل متقارن تهی باشه یه معنی تساوی دو زبان منظم هست
[tex]L_{1}\Theta L_{2}=L[/tex]
[tex]L=\phi[/tex]
(۱۶ بهمن ۱۳۹۲ ۰۶:۴۷ ب.ظ)hosshah نوشته شده توسط:تساوی دو زبان منظم تصمیم پذیره. حتی زیرمجموعه بودنش هم تصمیم پذیره.(16 بهمن ۱۳۹۲ ۰۶:۲۶ ب.ظ)mahsalove نوشته شده توسط: آخر این صفحه گفتم چرا مساوی بودن رو باید چک کنیم !و توسط حافظه مستقل از متن نمی توان این مساوی بودن رو چک کرد!ولی یه سوال کی گفته مساوی بودن دو مجموعه منظم تصمیم پذیر است؟!:/مساوی بودنی که مستقل از متن نمی تونه انجام بده منظم که محدودتره می تونه انجام بده!مساوی بودن جز مسائل تصمیم ناپذیره مستقل از متنه!:/
در مورد این زبان که مثل اینکه اصلا من متوجه نشده بودم و بله منظم و مستقل ازمتن نیست. اما وقتی میگم تساوی دو زبان منظم تصمیم پذیره یعنی میتونیم yes یا no بدیم
الگوریتم تساوی دو زبان مستقل ازمتن هم میتونه محاسبه تفاضل متقارن باشه. اگر حاصل تفاضل متقارن تهی باشه یه معنی تساوی دو زبان منظم هست
[tex]L_{1}\Theta L_{2}=L[/tex]
[tex]L=\phi[/tex]
که خب ظاهرا ارتباطی با این سوال نداشت چون به نظر خودم wها میتونن به شکلی باشن که منظم نباشن.
فکر میکنم توضیح بیشترم بی فایده باشه
موفق باشین
در پایان به عبارت زیر نگاه کنید
[tex]L_{1}\Theta L_{2}=(L_{1}-L_{2})\bigcup (L_{2}-L_{1})[/tex]
(۱۶ بهمن ۱۳۹۲ ۰۷:۰۵ ب.ظ)hosshah نوشته شده توسط: فکر میکنم توضیح بیشترم بی فایده باشه
موفق باشین
در پایان به عبارت زیر نگاه کنید
[tex]L_{1}\Theta L_{2}=(L_{1}-L_{2})\bigcup (L_{2}-L_{1})[/tex]
بلی الان متوجه منظورتون شدم پس منظم بودن چون تحت تفاضل متقارن بستست و می شه مساوی بودن رو تحت این عملگر حساب کرد پس تصمیم پذیره ولی مساوی بودن زبان مستقل از متن تصمیم پذیر نیست مرسی که بهم ثابت کردید
