من توی تشخیص زبانهای خطی خیلی مشکل دارم و معمولا هم اشتباه میکنم .دوستان کسی میتونه یه راه به من نشون بده؟
گرامر G رو خطی میگیم در صورتی که کلیه قوانین آن به صورت
A->xB
یا
A->Bx
یا
A->x
که A,B E V
مثلا
AB-->a خطی نیست
A-->BC خطی نیست.
ولی A-->abB خطی (خطی راست) است.
A--->Bab هم خطی (خطی چپ) است.
و البته اینم خطیه:A-->aBb
(۲۴ دى ۱۳۸۹ ۰۷:۲۴ ب.ظ)afagh1389 نوشته شده توسط: گرامر G رو خطی میگیم در صورتی که کلیه قوانین آن به صورتمن گفتم زبان خطی .اینکه گرامره !!!!!!!!!!!!نمیشه که تو کنکور بشینم گرامر بنویسم!!!!!!!!!!!!!!!!!!
A->xB
یا
A->Bx
یا
A->x
که A,B E V
: سمت چپ فقط و فقط یک متغیر و در سمت راست حداکثر یک متغیر (حرف بزرگ) و هر تعداد حرف کوچک میتواند قرار بگیرید.
مثلا
AB-->a خطی نیست
A-->BC خطی نیست.
ولی A-->abB خطی (خطی راست) است.
A--->Bab هم خطی (خطی چپ) است.
حالا چرا میزنید
خوب من جایی ندیدم که بگن این زبان خطی هست یا نه من فقط دیدم روی خطی بودن گرامر بحث میشه.
میتونید نمونه سوال رو بگذارید!
دوستمون afagh1389 خیلی خوب راهنمایی تون کردن...برای اینکه تشخیص بدین یه زبان خطی هست یا نه باید ببینین که براش گرامر خطی وجود داره یا نه! فکر نمی کنم راه دیگه ای باشه.اگه هست دوستان راهنمایی کنن!
البته اگه زبان منظم باشه ،حتما خطی هست.
مثلا این: a^i b^j c^i d^k و i, k, j>0
(۲۴ دى ۱۳۸۹ ۱۱:۴۳ ب.ظ)mehr.iman نوشته شده توسط: و البته اینم خطیه:A-->aBbببخشید مطمئن هستید؟؟ آخه من جایی ندیدم این رو خطی بگیره فکر میکنم توی خطی باید ترمینالها یک طرف متغیر باشند؟
گرامر زبان میشه
S-->aSb|cC
C-->cC|dD
D--->dD|lambda
تشخیص خطی بودنش با خودتون!!
دوستان چرا از لم تزریق برا اینکه بفهمیم خطی هست یا نه استفاده نمیکنید؟
قضیه ۲-۸ لینز
در ضمن شکل سلسله مراتب چامسکی را یادتون نره که:
اگر زبانی خطی باشه ممکن است قطعی باشه ممکنم هست قطعی نباشه اما در کل مستقل ازمتنه مثل:
L={a^nb^n}U{a^nb^2n}ooooooo که خطی هست اما قطعی نیست
(۲۵ دى ۱۳۸۹ ۱۰:۲۸ ب.ظ)afagh1389 نوشته شده توسط:(24 دى ۱۳۸۹ ۱۱:۴۳ ب.ظ)mehr.iman نوشته شده توسط: و البته اینم خطیه:A-->aBbببخشید مطمئن هستید؟؟ آخه من جایی ندیدم این رو خطی بگیره فکر میکنم توی خطی باید ترمینالها یک طرف متغیر باشند؟
با توجه به تعریفی که خودتون ارائه دادین بله!
گرامر خطی که فقط مربوط به زبونای منظم نیست،گرامر مستقل از متن خطی هم داریم.
گرامر مستقل از متنی که سمت راستش حداکثر یه غیرپایانه بیاد خطیه.
اکثرا فک میکنن خطی فقط برا زبونای منظمه(خطی از راست و خطی از چپ)،ولی اونی که من گفتمم خطیه.
(۲۵ دى ۱۳۸۹ ۱۰:۴۴ ب.ظ)hsh88 نوشته شده توسط: دوستان چرا از لم تزریق برا اینکه بفهمیم خطی هست یا نه استفاده نمیکنید؟با لم تزریق مگه میشه خطی بودن زبونو تشخیص داد؟
قضیه ۲-۸ لینز
در ضمن شکل سلسله مراتب چامسکی را یادتون نره که:
اگر زبانی خطی باشه ممکن است قطعی باشه ممکنم هست قطعی نباشه اما در کل مستقل ازمتنه مثل:
L={a^nb^n}U{a^nb^2n}ooooooo که خطی هست اما قطعی نیست
لم تزریق برای مستقل از متنا برا تشخیص مستقل از متن بودن یا نبودنه.
در مورد قطعی بودنم بحثی نشد!،اما همونطور که میدونید هر LL(K) ای قطعیه و اگه گرامرو دادن گفتن زبونش قطعیه یا نه باید ببینید LL(K) هست یا نه.
در مورد اون زبونی که گفتین اگه اینجوری بود قطعی میشد:
L={j a^n b^n} U {k a^n b^2n
ولی Reverseاون دیگه قطعی نیست.
(۲۵ دى ۱۳۸۹ ۰۵:۳۶ ب.ظ)jaroon نوشته شده توسط: مثلا این: a^i b^j c^i d^k و i, k, j>0در مورد این زبون لازم نیست حتما بشینین گرامرشو بنویسین،اگه دقت کنین میبینین تعداد bوd برامون مهم نیست و مهم برابر بودن تعداد aوc هست و میشه مثل a^n b^n پس خطیه.
در کل بعضی اوقات اینجوری میشه تشخیص داد بعضی اوقاتم اگه چاره ای نباشه باید گرامر نوشت،اگه دوستان راه دیگه ای بلدن ممنون میشم بگن.
از کجا میفهمید b^n a^n خط[/code]یه؟
(۲۵ دى ۱۳۸۹ ۱۱:۵۲ ب.ظ)jaroon نوشته شده توسط: از کجا میفهمید b^n a^n خط[/code]یه؟این یکیو دیگه سعی کنید گرامرشو حفظ کنید:
S-->aSb|Lombda
موفق باشین
دوست عزیز به آدرس قضیه ایی که گفتم مراجعه کن و شرط لم ترزیق برای خطی نبودن را دقیق بخون
منظور من را اشتباه متوجه شدی به دوتا نمودار سلسله چامسکی دقت کن با اون نمودار خیلی از مسائل حل میشه