گرامر خطی

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

مثال

یک گرامر خطی ساده G که {N = {S}, Σ = {a, b و P با نماد شروع S و قواعد:

• S → aSb
• S → ε

که زبان $\{a^{i}b^{i}\;|\;i\geq 0\}$ را تولید می‌کند.

ارتباط با گرامر منظم

دو نوع خاص از گرامر خطی به شرح زیر است:

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

نوع خاص دیگری از گرامر خطی به شرح زیر است:

گرامر خطی که در آن همه نمادهای غیرپایانی در طرف راست در پایان‌های راست یا چپ هستن، ولی نه لزوماً در یک انتهای یکسان.

با قرار دادن غیرپایانی‌های جدید، هر گرامر خطی را می‌توان بدون تحت تأثیر قرار دادن زبان تولید شده، به این فرم درآورد. به عنوان مثال قوانین G فوق را می‌توان جایگزین کرد با:

• S → aA
• A → Sb
• S → ε

از این رو، گرامر خطی با این فرم خاص می‌تواند تمامی زبان‌های خطی را تولید کند.

قدرت بیان

دیدیم که همهٔ زبان‌های منظم خطی هستند؛ مثال بالا یک زبان غیر منظم خطی بود. طبق تعریف تمامی زبان‌های خطی مستقل از متن هستند؛ مثال ساده‌ای از زبان غیرخطی مستقل از متن زبان Dyck از جفت براکت‌های متعادل شده است. از این رو، زبان‌های منظم زیرمجموعهٔ مناسبی از زبان‌های خطی هستند که به نوبهٔ خود زیرمجموعهٔ مناسبی از زبان‌های مستقل از متن می‌باشند.

در حالی که زبان‌های خطی که زبان‌های منظم هستند قطعی می‌باشند، زبان‌های خطی ای وجود دارد که غیر قطعی هستند.

برای مثال، زبان پالیندروم با طول زوج، روی الفبای ۰ و ۱ گرامر خطی ای به صورت S → 0S0 | 1S1 | ε دارد. رشته دلخواه از این زبان نمی‌تواند بدون خواندن تمامی حروفش برای اولین بار تجزیه شود؛ به این معنی که یک اتومات پشته‌ای باید انتقال حالت‌های جایگزین را برای تطبیق دادن رشته‌های تجزیه طول‌های ممکن مختلف امتحان کند. این زبان غیرقطعی است. از آنجا که زبان مستقل از متن غیرقطعی نمی‌تواند در زمان خطی پذیرفته شود، در حالت کلی زبان خطی نمی‌تواند در زمان خطی پذیرفته شود.

علاوه براین، نمی‌توان راجع به اینکه زبان مستقل از متن داده شده زبان مستقل از متن خطی نیز هست یا نه نظر داد.

ویژگی‌های بسته بودن

اگر L یک زبان خطی و M یک زبان منظم باشد، در نتیجه اشتراک $L\cap M$ نیز یک زبان خطی است. به عبارت دیگر، زبان‌های منظم تحت عمل اشتراک با مجموعه‌های منظم بسته هستند. علاوه بر این، زبان‌های خطی تحت همریختی و همریختی معکوس نیز بسته هستند.

این سه ویژگی بسته شدن نشان می‌دهد که زبان‌های خطی تشکیل یک گروه سه تایی کامل را می‌دهند. گروه‌های سه تایی کامل به طور کلی خانواده‌های زبانی هستند که از چند ویژگی ریاضی مطلوب استفاده می‌کنند.

منابع

• ویکی‌پدیای انگلیسی