سلام
تو فصل ۱۱ کتاب لینز یه شکل کشیده که زبانهای منظم زیرمجموعه محض زبانهای خطی هستند اما من یه جا دیدم یه زبان مستقل از متنو که خطی نبود منظم میدونست. حالا سوالم اینه میشه زیونی منظم باشه اما خطی نباشه؟
پیشاپیش ممنون
(۰۹ آبان ۱۳۹۲ ۱۰:۵۱ ق.ظ)SnowBlind نوشته شده توسط:(09 آبان ۱۳۹۲ ۰۸:۲۵ ق.ظ)zimenswall نوشته شده توسط: مشکل برخورد کردم که گاهی گرامر خطی نبوده ولی زبانش منظم بوده.هر خطی ای منظم نیست، باید خطی از راست و یا چپ باشه.
البته شرط لازم و کافی برای منظم بودن اینه که گرامر خطی براش باشه ولی شرطی گفته نشده که اگر گرامر ناخطی باشه حتما نامنظمه.
من در همین میدونم
ممنون که اصلاحش کردید. حواسم نبود بنویسم خطی راست یا چپ. همیشه هم این مشکل را دارم.
(۰۹ آبان ۱۳۹۲ ۱۰:۵۱ ق.ظ)SnowBlind نوشته شده توسط:(09 آبان ۱۳۹۲ ۰۸:۲۵ ق.ظ)zimenswall نوشته شده توسط: مشکل برخورد کردم که گاهی گرامر خطی نبوده ولی زبانش منظم بوده.هر خطی ای منظم نیست، باید خطی از راست و یا چپ باشه.
البته شرط لازم و کافی برای منظم بودن اینه که گرامر خطی براش باشه ولی شرطی گفته نشده که اگر گرامر ناخطی باشه حتما نامنظمه.
من در همین میدونم
ممنون که اصلاحش کردید. حواسم نبود بنویسم خطی راست یا چپ. همیشه هم این مشکل را دارم.
زبانش این بوده:
S -> aSb | bSa | AB
A -> aA | a
B -> bB | b
این زبان خطی نیست و مستقل از متنه. ولی حالا چطور می تونه منظم باشه؟؟؟ [/align]
(۰۹ آبان ۱۳۹۲ ۰۴:۲۸ ب.ظ)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]
زبانش ساده میشه و همون سیکما استاره.