دستور زبان منظم: تفاوت میان نسخه‌ها

در [[علم رایانه]]، قواعد [[دستور زبان]] به نوعی دستور [[زبان رسمی]] اطلاق می‌شود که قواعد یک زبان را توصیف می‌کند.

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

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

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