سلام
دوستان امکانش هست درستی با نادرستی هر یک از جملات رو مشخص کنید؟
۱) هر گرامر منظم لزوما غیر مبهم است.
۲) برای هر زبان منظم لزوما یک گرامر غیر مبهم وجود دارد.
۳) زبان هر گرامر ساده یک زبان منظم است.
۴) مجموعه همه عبارت های منظم روی الفبا [tex]Sigma\: =\: \{\: a\: ,\: b\: \}[/tex] یک مجموعه مستقل از متن است.
۵) مجموعه گرامرهای مستقل از متن ساخته شده از روی مجموعه متغیرها و پایانه های به ترتیب V و T یک مجموعه منظم است.
به نظر خودم ۱ و ۳ نادرستن . ۲ و ۴ هم درست هستن. اما در مورد ۵ نظری ندارم. ممنون میشم کمک کنید
سلام
دو نکته :
۱/ یک زبان منظم هیچگاه ذاتا مبهم نیست.
۲/ یک گرامر ساده مبهم نیست.
پس ممکن است گرامر منظمی باد که مبهم باشد اما ذاتا مبهم نیست. (گزینه یک غلط)
با توجه به اینکه "یک زبان منظم هیچگاه ذاتا مبهم نیست" پس حتما گرامر غیرمبهمی دارد. (گزینه دو درست)
در مورد گزینه سوم با تردید میگم غلط هست.
دوتای آخر هم مشخص نیست چی هست!
(۰۶ دى ۱۳۹۴ ۰۴:۳۸ ب.ظ)digicom نوشته شده توسط: سلام
دو نکته :
۱/ یک زبان منظم هیچگاه ذاتا مبهم نیست.
۲/ یک گرامر ساده مبهم نیست.
پس ممکن است گرامر منظمی باد که مبهم باشد اما ذاتا مبهم نیست. (گزینه یک غلط)
با توجه به اینکه "یک زبان منظم هیچگاه ذاتا مبهم نیست" پس حتما گرامر غیرمبهمی دارد. (گزینه دو درست)
در مورد گزینه سوم با تردید میگم غلط هست.
دوتای آخر هم مشخص نیست چی هست!
برای شماره ۳، به نظر من هم نادرسته. من زبان L رو در نظر گرفتم.
[tex]L\: =\: a^nb^n[/tex]
که گرامر سادش به این شکله
[tex]ُS\: \longrightarrow\: aX[/tex]
[tex]X\: \longrightarrow\: a\: X\: B[/tex]
[tex]X\: \longrightarrow\: b[/tex]
[tex]B\: \longrightarrow\: b[/tex]
از طرفی میدونیم که زبان L منظم نیست. به همین خاطر من میگم عبارت شماره ۳ نادرسته.
(۰۶ دى ۱۳۹۴ ۰۵:۵۵ ب.ظ)robin1 نوشته شده توسط: به نظر من
۱)درسته چون زبان منظم ممکنه براش چندتا اشتقاق باشه ولی گرامر منظم چون یا خطی چپه یا راست پس غیر مبهمه
۲)درسته چون واسه هر زبان منظم میشه گرامر خطی چپ و راست نوشت و اونا هم که غیر مبهمن
۳)درسته چون درقاعدش(نتونستم بنویسم) زوج (A,a) نمیتونه تکرار بشه پس نمیتونه حافظه هم داشته باشه پس منظمه
۴)نتونستم بخونم
۵)نظری ندارم
برای جمله اول گرامر منظم پایین رو در نظر گرفتم. برای رشته w = aa طبق این گرامر دو تا اشتقاق چپ وجود داره. پس گرامر رو پیدا کردم که در عین مبهم بودن، منظم هم هست.
[tex]S\: \longrightarrow\: a\: B\: |\: A[/tex]
[tex]ُ\: A\: \longrightarrow\: a\: A\: \mid\: \lambda[/tex]
[tex]ُ\: B\: \longrightarrow\: b\: B\: \mid\: a[/tex]
پس جمله اول نادرست هست. چیزی که میگم درسته؟
من گرامر نمیتونم بخونم ولی حتما باید یا خطی راست باشه یا چپ
(۰۶ دى ۱۳۹۴ ۰۷:۵۵ ب.ظ)robin1 نوشته شده توسط: من گرامر نمیتونم بخونم ولی حتما باید یا خطی راست باشه یا چپ
فرستاده شده از HTC Sensation XE with Beats Audio Z715eِ من با Tapatalk
گرامری هم که من نوشتم خطی راست هست.
یه سئوال
از کجا باید بفهمیم که یک زبان مستقل از متن مبهم یا خیر؟
اگه مبهمه چطور باید بفمیم آیا غیر میهم برای آن وجود دارد یانه ؟!
با تشکر
(۰۹ دى ۱۳۹۴ ۰۵:۱۱ ب.ظ)iCanDoIt نوشته شده توسط: یه سئوال
از کجا باید بفهمیم که یک زبان مستقل از متن مبهم یا خیر؟
اگه مبهمه چطور باید بفمیم آیا غیر میهم برای آن وجود دارد یانه ؟!
با تشکر
سلام
اگر رشته ای عضو زبان پیدا کردی که براش دو تا اشتقاق چپ یا دو تا اشتقاق راست یا دو تا درخت تجزیه متفاوت وجود داشت، اون زبان مبهم هست.
(۰۹ دى ۱۳۹۴ ۰۵:۱۱ ب.ظ)iCanDoIt نوشته شده توسط: یه سئوال
از کجا باید بفهمیم که یک زبان مستقل از متن مبهم یا خیر؟
اگه مبهمه چطور باید بفمیم آیا غیر میهم برای آن وجود دارد یانه ؟!
با تشکر
سلام
زبان مستقل از متن رو میشه از روش پوش و پاپ پشته شناخت ویاخطی بودن که منظم می شه زبان و در نهایت مستقل از متن میشه
یه راه دیگه هم هست که خیلی نزدیک راه پیدا کردن زبان منظم هست که اون اینه که اگه رشته های زبان بی حساب زیاد بود مستقل ازمتن نیست
علایم ابهام رو میشه به صورت تستی گفت : چپ گردی و راست گردی همزمان متغیر و یا میان وندی -بازگشت به متغیر اولیه بعد از چند بار اشتقاق
و ذاتا مبهم رو باید از درخت اشتقاق استفاده کرد.
البته تمام راههای بالا با تست حل کردن زیاد هست که جا میفته دوست عزیز