سلام
تو فصل 11 کتاب لینز یه شکل کشیده که زبانهای منظم زیرمجموعه محض زبانهای خطی هستند اما من یه جا دیدم یه زبان مستقل از متنو که خطی نبود منظم میدونست. حالا سوالم اینه میشه زیونی منظم باشه اما خطی نباشه؟
پیشاپیش ممنون
(09 آبان 1392 10:51 ق.ظ)SnowBlind نوشته شده توسط: [ -> ] (09 آبان 1392 08:25 ق.ظ)zimenswall نوشته شده توسط: [ -> ]مشکل برخورد کردم که گاهی گرامر خطی نبوده ولی زبانش منظم بوده.
البته شرط لازم و کافی برای منظم بودن اینه که گرامر خطی براش باشه ولی شرطی گفته نشده که اگر گرامر ناخطی باشه حتما نامنظمه.
من در همین میدونم
هر خطی ای منظم نیست، باید خطی از راست و یا چپ باشه.
ممنون که اصلاحش کردید. حواسم نبود بنویسم خطی راست یا چپ. همیشه هم این مشکل را دارم.
(09 آبان 1392 10:51 ق.ظ)SnowBlind نوشته شده توسط: [ -> ] (09 آبان 1392 08:25 ق.ظ)zimenswall نوشته شده توسط: [ -> ]مشکل برخورد کردم که گاهی گرامر خطی نبوده ولی زبانش منظم بوده.
البته شرط لازم و کافی برای منظم بودن اینه که گرامر خطی براش باشه ولی شرطی گفته نشده که اگر گرامر ناخطی باشه حتما نامنظمه.
من در همین میدونم
هر خطی ای منظم نیست، باید خطی از راست و یا چپ باشه.
ممنون که اصلاحش کردید. حواسم نبود بنویسم خطی راست یا چپ. همیشه هم این مشکل را دارم.
زبانش این بوده:
S -> aSb | bSa | AB
A -> aA | a
B -> bB | b
این زبان خطی نیست و مستقل از متنه. ولی حالا چطور می تونه منظم باشه؟؟؟ [/align]
(09 آبان 1392 04:28 ب.ظ)hap777 نوشته شده توسط: [ -> ]زبانش این بوده:
S -> aSb | bSa | AB
A -> aA | a
B -> bB | b
این زبان خطی نیست و مستقل از متنه. ولی حالا چطور می تونه منظم باشه؟؟؟ [/align]
سلام. این زبان که شما نوشتید منظم نیست. ولی دلیل منظم نبودنش خطی نبودنش نیست.
هر زبان منظم (یا مستقل از متن یا هر نوع دیگه) با قواعد زبانهای قوی تر قابل نمایشه. یعنی میشه یه زبان منظم رو با گرامر مستقل از متن یا ماشین تورینگ طراحی کرد. مثلاً زبان زیر منظمه:
[tex]S\to aS|bS|\lambda|aSbb|aAAab[/tex]
[tex]A\to aAab|bba[/tex]
زبانش ساده میشه و همون سیکما استاره.