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

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

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