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

دوستان میشه تعریف خودمونی زبانهای خطی منظم و مستقل از متنو بفرمایید؟

سلام. زبان خطی زبانیه که گرامرش فقط شامل یه غیرپایانه در سمت راست باشه.
اگه تمام قواعد هم بصورت چپ خطی یا راست خطی باشن یعنی تمام غیر پایانه های سمت راست، همشون در سمت چپ یا سمت راست باشه اون موقع منظم میشه.

(30 دى 1393 01:59 ق.ظ)ریحان نوشته شده توسط: [ -> ]ممنونم.اونوقت مستقل از متن خطی هم همینطور؟

متوجه نمیشم. زبانهای خطی زیرمجموعه از مستقل از متنن. اگه تمام قواعد بفرم چپ خطی یا همشون به فرم راست خطی باشن اون موقع زبان منظمه. مثلاً زبان زیر منظمه:

[tex]S\to aabaS|aaA|abA|bB[/tex]
[tex]A\to aabaaA|aaB|bba[/tex]
[tex]B\to aaB|ab[/tex]

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

منظورم این بود که تعریف زبان مستقل از متن خطی هم همینه؟ که 1 متغیر در سمت راست قواعدش باشه؟

(30 دى 1393 02:30 ق.ظ)ریحان نوشته شده توسط: [ -> ]منظورم این بود که تعریف زبان مستقل از متن خطی هم همینه؟ که ۱ متغیر در سمت راست قواعدش باشه؟

بله.

ممنون