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

مستقل از متن (همومورفیزم و wawR)

ارسال:
  

sepehr . kh پرسیده:

Lightbulb مستقل از متن (همومورفیزم و wawR)

سلام دوستان، خسته نباشید
چنتا سوال بحث بر انگیز نظریه زبان داشتم؛ جوابشونا شک دارم، اگر ممکنه کمک کنید!
_ زبان های مستقل از متن تحت همریختی (همومورفیک) بسته نمی باشند؟؟ داخل کتاب نوشته هست، اما در تست سال ۸۵ و ... گفته نمیباشد!
_ زبان {WaZ| Z =! wR} (=! بمعنی غیر مساوی) و همچنین {(*wzwR| w,z E (a,b} (یعنی w,zرشته میباشند) مستقل ازمتن نمیباشند دیگه؟؟ چرا؟؟

۱
ارسال:
  

Hamid_0311 پاسخ داده:

RE: سوالات بجث برانگیز نظریه زبان!

با سلام دوست عزیز زبان های مستقل از متن تحت همریختی بسته هستن اما زبان ها مستقل از متن قطعی خیر
در مورد سوالتون اگر منظورتون از زبان اول اینه
[tex]\{ waz\: |\: z\ne\: w^R \}[/tex]

که این زبان مستقل از متن اما اگر a جز الفبای زبان نباشه مستقل از متن قطعی و اگر باشه غیر قطعی هست در حالت اول شما میگی W بریز تو پشته به a که رسیدی بریزش دور حال از بالا پشته پاپ کن و با بقیه قیاس کن اگر به یک حالت تناقض رسیدی که باهم برابر نبودن یعنی رشته پذیرفته میشه اگر تا ته رشته رفتیم و پشته خالی شد و به تناقض نرسیدیم رشته پذیرفته نمیشه
اما در حالت دوم مثل همینه اما غیر قعطی میگیم این کارو بکن چون نمیدونیم وسط رشته دقیقا کجاس و میگیم به وسط رشته رسیدی یک a بخون و بعد از a با بالای پشته قیاس کن باید یک تناقض پیدا کنیم بقیه اش مثل همون حالت اوله

اما زبان بعدی
[tex]\{ wzw^R\: |\: \: z,\: w\: \in\: Sigma\: ^{\ast\: } \}[/tex]

این زبان یک زبان منظم هستش و میدونیم هر زبان منظمی مستقل از متن قطعی پس مستقل از متن هم هست
چرا منظم؟ قبول دارید که رشته های که این زبان تولید می کنه زیر مجموعه از
[tex](a b)^{\ast}[/tex]
هستش؟ هر رشته ای تولید می کنه بلاخره یه تعدادی a یا b هستش دیگه
خوب حالا ایا قبول دارید که
[tex](a b)^{\ast}[/tex]
هم زیر مجموعه این هستش
[tex]\{ wzw^R\: |\: \: z,\: w\: \in\: Sigma\: ^{\ast\: } \}[/tex]

چون شما اینو
[tex](a b)^{\ast}[/tex]
Z در نظر بگیر
و w را هم رشته لاندا در نظر بگیر
زبان قبولش میکنه یا نه؟
خوب طبق ریاضی هم داریم
[tex]if\: A\subseteq\: B\: And\: B\subseteq\: A\: \longleftrightarrow\: A=\: B[/tex]

خوب زبان پس میشه
[tex](a b)^{\ast}[/tex]
که این زبانم میدونیم همون سیگما استار و منظم هست امیدوارم متوجه شده باشید موفق باشیدBig Grin

۰
ارسال:
  

sepehr . kh پاسخ داده:

RE: مستقل از متن (همومورفیزم و wawR)

بسیار ممنونم از لطفتون دوست عزیز
بله؛ بسیار هم عالی توضیح دادید!
_منم مستقل ازمتن را نسبت به همریخته بسته میدونستم، اما در ۲ تست سراسری این چنین نبوده!
مثلا(سراسری ۸۵): کدام یک از عبارات زیر صحیح نمی باشد؟ (کتاب پوران گزینه ۲ را کلید اعلام کرده)
۱)الگوریتمی برای تصمیمگیری گرامر مستقل از متن((L(G) تهی است یا نه وجود دارد
۲)زبان های مستقل از متن تحت همریختی بسته
۳)زبان های خطی تحت همریختی بسته
۴)الگوریتمی برای تصمیمگیری گرامر مستقل از متن((L(G) متناهی است یا نه وجود دارد
_ چه توضیح قشنگی! ممنون. میشه یه راه کلی برای تشخیص مستقل از متن غیر قطعی و قطعی بگید؟؟ یکم گیج شدم وتسلطم کمه
مثلا WW^R غیر قطعی میباشد؟! چون به پشته غیر قطعی که وسط رشته را تشخیص بدیم نیاز داریم
_بله کاملا معلومه برابر Z* میباشد! بی دقتی کردم
بازم ممنون، همیشه موفق باشید

۰
ارسال:
  

Hamid_0311 پاسخ داده:

RE: مستقل از متن (همومورفیزم و wawR)

با سلام ببینید این تست که هر ۴ گزینه درسته حالا شاید توی این اشتباه تایپی هست بهتره برید کلید سنجش ببنید و یا از روی کتاب دیگه چک کنید کتاب پورانم بچه ها میگن خیلی غلط داره (ماله سهرابی) دیگه نمیدونم ولی این تستی که نوشتین هر ۴ گزینه درسته

اما در مورد زبان قطعی غیر قطعی راه حل قطعی نداریم و باید یه تجسمی بکنید از اینکه چطوری اون رشته هارو می پذیره و ایا هر مرحله که می خواهد ماشین کاری انجام بده یک راه مشخص داره یا نه

مثلا توی همینی که نوشتید چرا میگیم غیر قطعی؟ چون نمیدونه وسط رشته دقیقا کی هست و از کی باید شروع کنه از بالای پشته پاپ کردن و قیاس کردن
یا توی حالتی که
[tex]\{a^nb^n\}\: \: \cup\: \: \{a^nb^{2n}\}[/tex]

ماشین وقتی به b ها میرسه نمیدونه که باید به ازای هر یک b یک a پاپ کنه یا به ازای هر ۲ تا b یک a پس هیچ قطعیتی نیست و میگیم غیر قطعی تصمیم میگیره
البته نظریه هر چی بیشتر مدل ها و تایپ های مختلف ببینید زودتر مسلط میشید ولی خوب فک کنم بچه ها میگفتن توی کتاب پارسه چند صفحه ای زبان ها را خلاصه کرده شاید خوندنشون بد نباشه و اینکه واسه خودتون تحلیل کنید مثلا فلان زبان چطوری کار می کنه که قطعی یا غیر قطعی

دیگه چیز دیگه ای من به نظرم نمیرسهBig Grin موفق باشید

۰
ارسال:
  

sepehr . kh پاسخ داده:

RE: مستقل از متن (همومورفیزم و wawR)

بسیار ممنون دوست عزیز از پاسخ های کاملتون
لطف کردید؛ همیشه شاد و موفق باشید



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  متن به هم ریخته در نرم افزار Notepad HAMID3F ۱۵ ۲۲,۹۶۱ ۱۷ شهریور ۱۳۹۹ ۰۸:۲۶ ق.ظ
آخرین ارسال: rezasedghi100
  گرامر مستقل از متن Sanazzz ۴ ۵,۵۱۵ ۱۲ دى ۱۳۹۷ ۰۹:۵۹ ب.ظ
آخرین ارسال: Sanazzz
  متن ایمیل برای نویسنده مقاله Iran2014 ۲ ۳,۵۲۸ ۱۰ مهر ۱۳۹۷ ۰۹:۱۵ ب.ظ
آخرین ارسال: Iran2014
  متن کاوی zorro ۰ ۱,۸۶۸ ۲۸ بهمن ۱۳۹۶ ۰۷:۲۸ ب.ظ
آخرین ارسال: zorro
  منظور این متن در آمار چیست؟ H-Arshad ۰ ۱,۵۶۶ ۲۶ مهر ۱۳۹۶ ۰۳:۲۶ ق.ظ
آخرین ارسال: H-Arshad
  دیتاست برای بازیابی اطلاعات مانند تصویر و متن در شبکه های اجتماعی minamm ۰ ۲,۰۶۳ ۱۷ اردیبهشت ۱۳۹۶ ۱۰:۲۲ ق.ظ
آخرین ارسال: minamm
  حساس به متن و مستقل از متن kilookiloo ۲ ۲,۸۵۸ ۰۶ اردیبهشت ۱۳۹۶ ۰۷:۴۱ ق.ظ
آخرین ارسال: kilookiloo
  تعیین نوع زبان( مستقل از متن یا منظم) ازمون های آزمایشی AZ_AMIR ۲ ۳,۳۲۲ ۰۳ اردیبهشت ۱۳۹۶ ۰۷:۵۳ ب.ظ
آخرین ارسال: AZ_AMIR
  تشخیص زبان مستقل ازمتن قطعی mzha ۲ ۲,۰۶۴ ۲۲ دى ۱۳۹۵ ۱۰:۱۷ ب.ظ
آخرین ارسال: mzha
  کمک در پردازش متن با پایتون mariyG ۵ ۴,۰۹۸ ۱۹ آذر ۱۳۹۵ ۱۱:۲۹ ب.ظ
آخرین ارسال: mariyG

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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