تالار گفتمان مانشت

من توی تشخیص زبانهای خطی خیلی مشکل دارم و معمولا هم اشتباه میکنم .دوستان کسی میتونه یه راه به من نشون بده؟

گرامر G رو خطی میگیم در صورتی که کلیه قوانین آن به صورت
A->xB
یا
A->Bx
یا
A->x

که A,B E V
مثلا
AB-->a خطی نیست
A-->BC خطی نیست.
ولی A-->abB خطی (خطی راست) است.
A--->Bab هم خطی (خطی چپ) است.

و البته اینم خطیه:A-->aBb

(24 دى 1389 07:24 ب.ظ)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

(24 دى 1389 11:43 ب.ظ)mehr.iman نوشته شده توسط: [ -> ]و البته اینم خطیه:A-->aBb

ببخشید مطمئن هستید؟؟ آخه من جایی ندیدم این رو خطی بگیره فکر میکنم توی خطی باید ترمینالها یک طرف متغیر باشند؟

---

گرامر زبان میشه

S-->aSb|cC
C-->cC|dD
D--->dD|lambda
تشخیص خطی بودنش با خودتون!!

دوستان چرا از لم تزریق برا اینکه بفهمیم خطی هست یا نه استفاده نمیکنید؟
قضیه 2-8 لینز
در ضمن شکل سلسله مراتب چامسکی را یادتون نره که:
اگر زبانی خطی باشه ممکن است قطعی باشه ممکنم هست قطعی نباشه اما در کل مستقل ازمتنه مثل:
L={a^nb^n}U{a^nb^2n}ooooooo که خطی هست اما قطعی نیست

(25 دى 1389 10:28 ب.ظ)afagh1389 نوشته شده توسط: [ -> ]

(24 دى 1389 11:43 ب.ظ)mehr.iman نوشته شده توسط: [ -> ]و البته اینم خطیه:A-->aBb

ببخشید مطمئن هستید؟؟ آخه من جایی ندیدم این رو خطی بگیره فکر میکنم توی خطی باید ترمینالها یک طرف متغیر باشند؟

---

با توجه به تعریفی که خودتون ارائه دادین بله!
گرامر خطی که فقط مربوط به زبونای منظم نیست،گرامر مستقل از متن خطی هم داریم.
گرامر مستقل از متنی که سمت راستش حداکثر یه غیرپایانه بیاد خطیه.
اکثرا فک میکنن خطی فقط برا زبونای منظمه(خطی از راست و خطی از چپ)،ولی اونی که من گفتمم خطیه.

---

(25 دى 1389 10:44 ب.ظ)hsh88 نوشته شده توسط: [ -> ]دوستان چرا از لم تزریق برا اینکه بفهمیم خطی هست یا نه استفاده نمیکنید؟
قضیه 2-8 لینز
در ضمن شکل سلسله مراتب چامسکی را یادتون نره که:
اگر زبانی خطی باشه ممکن است قطعی باشه ممکنم هست قطعی نباشه اما در کل مستقل ازمتنه مثل:
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اون دیگه قطعی نیست.

---

(25 دى 1389 05:36 ب.ظ)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]یه؟

(25 دى 1389 11:52 ب.ظ)jaroon نوشته شده توسط: [ -> ]از کجا میفهمید b^n a^n خط[/code]یه؟

این یکیو دیگه سعی کنید گرامرشو حفظ کنید:
S-->aSb|Lombda
موفق باشین

دوست عزیز به آدرس قضیه ایی که گفتم مراجعه کن و شرط لم ترزیق برای خطی نبودن را دقیق بخون
منظور من را اشتباه متوجه شدی به دوتا نمودار سلسله چامسکی دقت کن با اون نمودار خیلی از مسائل حل میشه