دستور زبان منظم

یک گرامر منظم راست (که گرامر خطی از راست نیز نامیده می‌شود) دستور زبان رسمی است (N,∑ , p, S) که تمامی قواعد مجموعهٔ p به یکی از اشکال زیر در آن وجود دارند:

1. B -> B-a نماد غیرپایانی از N است و α یک ترمینال (پایان) از ∑
2. B -> B-aC و C جزئی از N هستند و α جزئی از ∑
3. B -> B-ε جزئی از N است و نمایانگر مجموعه تهی می‌باشد، یعنی طول مجموعه صفر است.

در گرامر منظم چپ (که گرامر خطی از چپ نیز نامیده می‌شود) تمامی قواعد از قالب‌های زیر تبعیت می‌کنند:

1. A -> a که A یک نماد غیرپایانی و جزئی از N است و α یک ترمینال (پایان) و جزئی از ∑
2. A -> Ba که A و B جزئی از N هستند و α جزئی از ∑
3. A -> ε که A جزئی از N و ε جزئی از مجموعهٔ خطی تهی است.

نمونه‌ای از گرامر منظم راست G با فرمول N = {S, A}, Σ = {a, b, c}, P شامل قواعد زیر است:

S -> aS

S -> bA

A -> ε

A -> cA

و S علامت آغاز است. این دستور زبان همان زبانی را توصیف می‌کند که در عبارت a*bc* وجود دارد.

گرامر منظم راست G هرچند طولانی‌تر، اما ساده‌تر همین توصیف را برای عبارت N = {S, A, B, C}, ∑ = {a, b, c} توضیح می‌دهد که p در آن شامل قواعد زیر است:

S -> A

A -> aA

A -> B

B -> bC

C -> ε

C -> cC

هر یک از حروف بزرگ معادل عباراتی هستند که در عبارت قاعده‌مند بعدی آغاز می‌شوند. یک گرامر منظم یک گرامر منظم راست یا چپ است. بعضی از کتب و مقالات قواعد مجموعهٔ تهی را رد می‌کنند و فرض را بر این می‌گیرند که مجموعهٔ تهی در زبان‌ها وجود ندارد.

گرامر منظم راست تعمیم‌یافته، گرامری است که از یکی از قواعد زیر تبعیت می‌کند:

1. B -> a که B در اینجا نماد غیرقطعی و جزئی از N و α یک نماد قطعی در ∑ است.
2. A -> wB که A و B جزئی از N و w جزئی از *∑ هستند
3. A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

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

1. A -> a که A یک نماد غیرقطعی و جزئی از N است و α یک نماد قطعی و جزئی از ∑
2. A -> Bw که A و B جزئی از N هستند و w جزئی از *∑
3. A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

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

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

مشارکت‌کنندگان ویکی‌پدیا. «Universal Turing machine». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئن ۲۰۱۳.