منم میگم منظمه اما به هیچ پایانه ای ختم نمیشه چطور میگید متناهی درسته که بر نمیگرده اما تو satisfy یک یا چند مرحله به این رسیده من ۴ زدم چون احساس کردم satisfy شده پس برمیگرده ؟
اینکه A--->b چه مشکلی داره؟!!
اتفاقا به نظر من خیلی زود پایان می پذیره چون بازگشت نداره و سریع سمبل های پایانی جایگزین قواعد میشن.
نمیشه سوالا رو بدین به دکتر قدسی زحمت حلشو بکشن؟!!؟
(۰۱ اسفند ۱۳۸۹ ۱۱:۰۴ ق.ظ)bahar نوشته شده توسط: منم میگم منظمه اما به هیچ پایانه ای ختم نمیشه چطور میگید متناهی درسته که بر نمیگرده اما تو satisfy یک یا چند مرحله به این رسیده من ۴ زدم چون احساس کردم satisfy شده پس برمیگرده ؟
حرف های عجیب می زنیدا . از کجای اون شرط این برداشت رو کردید که گرامر به هیچ پایانه ای ختم نمی شه . مثلا گرامر زیر:
S->A
A->b
آیا این گرامر اون شرط رو نداره، آیا نتونسته پایانی تولید کنه . معنی اون شرط اینه که هیچ غیر پایانه ای در گرامر در ۱ یا بیشتر مرحله اشتقاق هرگز به خودش نمی رسد . با همین گرامر بالا می بینید که نمی شه حکم قطعی در مورد بی پایان بودن گرامر دارد.
(۰۱ اسفند ۱۳۸۹ ۱۱:۰۶ ق.ظ)afagh1389 نوشته شده توسط: اینکه A--->b چه مشکلی داره؟!!
اتفاقا به نظر من خیلی زود پایان می پذیره چون بازگشت نداره و سریع سمبل های پایانی جایگزین قواعد میشن.
نمیشه سوالا رو بدین به دکتر قدسی زحمت حلشو بکشن؟!!؟
قدسی استاد همه درسها نیست که!
پس در نهایت به منظم بودن آن شکی نیست اما بین ۲ گزینه ۲ و ۴ نظر دوستان دیگه هم مهمه ///؟
(۳۰ بهمن ۱۳۸۹ ۰۸:۴۳ ب.ظ)Mansoureh نوشته شده توسط:(30 بهمن ۱۳۸۹ ۰۸:۳۰ ب.ظ)arshad90 نوشته شده توسط: منم ۵۹ رو ۴ زدم. دقت کنید گ ۲ حالت خاصی از گ۴ هست. یعنی گ۴ ممکنه رسته های گ ۲ رو هم شامل شه و در نتیجه می شه گفت احتمال اینکه این گزینه، گزینه صحیح باشه بیشتره.
نه اشتباهه!!! گزینهی ۴ که bba رو میپذیره ولی شکل bba رو نمیپذیره!!! برای همین هم گزینهی ۴ غلطه!!
ببخشید، اما فکر می کنم منظور گزینهی ۴ رو به درستی متوجه نشدید! توی گزینهی ۴، تنها به فرم و صورت کلی رشته هایی که توسط ماشین پذیرفته میشن، اشاره شده و در مورد ماهیت w چیزی گفته نشده. گزینهی ۴ میگه: تمام رشته هایی که به صورت [tex]w(a b)^{*}[/tex] توسط ماشین پذیرفته میشن، توسط [tex]\bar{w}(a b)^{*}[/tex] هم پذیرفته میشن. هیچ جایی گفته نشده که الزاما w باید به صورت [tex]w\in\left( a b \right )^{*}[/tex] یا هر چیز دیگه ای باشه! به همین خاطر ما نمیتونیم بگیم گزینهی ۴، bba رو میپذیره!
از نظر من، هر دو گزینهی ۲ و ۴ کاملا صحیح می باشند! اما نظر طراح سوال رو نمیدونم!!!
حل سوال ۶۰ نظریه زبان بر طبق کتاب پیتر لینز صفحه ۲۱۸-تئوری ۸/۷:جملات دقیقا کلمه به کلمه به فارسی ترجمه شده است:
ما فرض می کنیم که G شامل هیچ کدام از قواعد لاندا-یکه و متغیر های مفید نیست. فرض می کنیم گرامر دارای یه متغیر تکرار شونده در قاعده خود است به طوریکه A متعلق به V (مجموعه غیر پایانی ها) است که برای آن یک اشتقاق وجود دارد.
وقتی فرض شده است که G هیچ قاعده لاندا-یکه و متغیر مفیدی ندارد پس x, y نمی توانند به طور همزمان تهی باشند. وقتی A هیچ متغیر nullable و یا متغیر مفید نیست پس ما داریم:
S=>uAv=>w و
A=>z
در اینجا u,v,z متعلق به T (مجموعه ترمینال یا پایانی) هستند. اما بنابراین:
S=>uAv=>ux^nAy^nv=>ux^nzy^n
و این برای تمامی n قابل قبول و امکان پذیر است بنابراین زبان G نامتناهی(بی پایان) است.
===
در ادامه پیتر لینز طریقه اصلاح چنین گرامری را توضیح داده.
اما بر می گردیم به سوال حالا گزینه های ۳ و ۴ با قسمت اول گفته آقای لینز برابر هستند. اما:
۱- همگی می دانیم زبانی منظم است که برای پذیرش آن بتوانیم یک FA طراحی کنیم(رجوع به کتاب لینز)
۲- گرامر سوال یک گرامر خطی است و می دانیم یک گرامر منظم همیشه خطی است ولی همه گرامر های خطی که منظم نیستند(رجوع به کتاب لینز)
۳- زبان منظم (نوع ۳) زبانی است که گرامر منظم داشته باشد یعنی یا خطی از راست یا خطی از چپ باشد.(رجوع به کتاب لینز)
۴- تعریف نامتناهی: یعنی از حالت شروع که حرکت کردیم حلقه داشته باشد به طوریکه از حالت شروع به آن راهی باشد و از آن به حالت نهایی راهی نباشد.
پس با توجه به نکات فوق گزینه ۳ یعنی زبان معادل آن بی پایان و نامنظم است صحیح است.
[attachment=433]
آخه گفته که زبان مستقل از متن است وهر زبان منظمی میتونه مستقل از متن باشه
بله قبول دارم که هر زبان منظمی مستقل از متن است اما آیا هر زبان مستقل از متنی هم منظم است در ضمن این توضیحاتی که گفتم مربوط به بخش خصوصیات زبان های مستقل از متن از کتاب لینز بود لطفا به کتاب صفحه ۲۱۸ تئوری ۸/۷ مراجعه کنید و یا عکس زمینه را دانلود کنید.این زبان اصلا منظم نیست.
دقت کنید که سوال دقیقا گفته ما متغیر تکراری نداریم و این یعنی متناهی بودن.
لطفا به بخشی که در کتاب گفتم مراجعه کنید.متغیر A تکرار شونده(خودگردان) است چون در قاعده خود خودش را صدا زده است و یک حلقه بوجود می آید جدای از اینکه u,v چه می خواهند باشند A تکرار شونده است مثلا S=>aSb.در ضمن این مطالب را من از خودم که نمی گم عینا در کتاب لینز این موضوع بحث شده.(رجوع به کتاب لینز-فصل خصوصیات گرامر های و زبان های مستقل از متن-ص۲۸۱-تئوری ۸/۷ و یا عکس ضمینه را دانلود و نگاه کنید.
ببینید من به کتاب مراجعه کردم و اونو خوندم قضیه برای اثبات متناهی بودن یا متناهی نبودن یه گرامر مستقل از متنه خوب تو سوال هم گفته هیچ متغیری تکراری نباشه شما یه بار سوال رو خوب بخون گفته قوانین بازگشتی نداریم و گفته هیچ یک از غیر پایانیها شرط A==>uAv رو نباید داشته باشه
(۰۲ اسفند ۱۳۸۹ ۰۲:۰۸ ق.ظ)sdcsada نوشته شده توسط:زبان نامنظم هست(هر چند کمی ابهام وجود داره،چون در مورد اینکه متغیرها کجای قواعد میتونه قرار بگیره مطلبی گفته نشده)،اما مطمئنا بی پایان نیست!چون شزط نامتناهی بودن اینه که قسمتی از گرامر دارای بازگشتی باشه(حالا چه مستقیم چه غیر مستقیم)،که شرط تعیین شده وجود بازگشت رو قانونی نمیدونه!
جملات دقیقا کلمه به کلمه به فارسی ترجمه شده است:
ما فرض می کنیم که G شامل هیچ کدام از قواعد لاندا-یکه و متغیر های مفید نیست. فرض می کنیم گرامر دارای یه متغیر تکرار شونده در قاعده خود است به طوریکه A متعلق به V (مجموعه غیر پایانی ها) است که برای آن یک اشتقاق وجود دارد.
وقتی فرض شده است که G هیچ قاعده لاندا-یکه و متغیر مفیدی ندارد پس x, y نمی توانند به طور همزمان تهی باشند. وقتی A هیچ متغیر nullable و یا متغیر مفید نیست پس ما داریم:
S=>uAv=>w و
A=>z
در اینجا u,v,z متعلق به T (مجموعه ترمینال یا پایانی) هستند. اما بنابراین:
S=>uAv=>ux^nAy^nv=>ux^nzy^n
و این برای تمامی n قابل قبول و امکان پذیر است بنابراین زبان G نامتناهی(بی پایان) است.
===
در ادامه پیتر لینز طریقه اصلاح چنین گرامری را توضیح داده.
اما بر می گردیم به سوال حالا گزینه های ۳ و ۴ با قسمت اول گفته آقای لینز برابر هستند. اما:
۱- همگی می دانیم زبانی منظم است که برای پذیرش آن بتوانیم یک FA طراحی کنیم(رجوع به کتاب لینز)
۲- گرامر سوال یک گرامر خطی است و می دانیم یک گرامر منظم همیشه خطی است ولی همه گرامر های خطی که منظم نیستند(رجوع به کتاب لینز)
۳- زبان منظم (نوع ۳) زبانی است که گرامر منظم داشته باشد یعنی یا خطی از راست یا خطی از چپ باشد.(رجوع به کتاب لینز)
۴- تعریف نامتناهی: یعنی از حالت شروع که حرکت کردیم حلقه داشته باشد به طوریکه از حالت شروع به آن راهی باشد و از آن به حالت نهایی راهی نباشد.
پس با توجه به نکات فوق گزینه ۳ یعنی زبان معادل آن بی پایان و نامنظم است صحیح است.
ویرایش: در هر صورت چون بازگشتی بودنا قانونی نمیدونه،فرقی نمیکنه کجای گرامر متغیر بیاد،بنابراین منظمه!
متاسفانه دوستان در مورد سوال ۶۰ نظرات متفاوتی میدن و نمی شه نتیجه گیری کرد.
دوستان ابتدا به ساکن بگید که آیا زبان یک گرامر با چنین شرایطی متناهی است یا نا متناهی؟
متناهی بودنش تا حدودی ملموسه، چون هیچ سمبلی بازگشت نداره. مگر این که خلافش دقیقا اثبات بشه (مثلا مثال نقض) یعنی یه گرامری بگید که بازگشت نداشته باشه ولی نامتناهی باشه. فعلا کاری با خطی و غیر خطی و ... نداریم.
اگر یک زبان متناهی باشه، منظمه، حالا گرامرش هر شکلی که می خواد داشته باشه.
ضمنا توجه کنید که اگر یک زبان نامنظم باشه حتما نامتناهی خواهد بود. (که در این صورت گزینه ۱ و گزینه ۴ دفترچه ۴۰۵A عین هم خواهند بود.)
اگر نامتناهی بود برای گزینه های دیگه دلیل بیارید.
ممنون
نظر منم اینه که چون متناهی است پس منظمه.
ممنون psps جان
من این سوال را نزدم ولی نظرم اینه که این زبان متناهی خواهد بود و چون متناهی است پس منظم است