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

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

:# B -> B-a نماد غیرپایانی از N است و α یک ترمینال (پایان) از ∑

:# B -> B-aC و C جزئی از N هستند و α جزئی از ∑

:# A -> Ba که A و B جزئی از N هستند و α جزئی از ∑

:# A -> ε که A جزئی از N و ε جزئی از مجموعۀمجموعهٔ خطی تهی است.

بعضی از کتب و مقالات قواعد مجموعۀمجموعهٔ تهی را رد می‌کنند و فرض را بر این می‌گیرند که مجموعۀمجموعهٔ تهی در زبان‌ها وجود ندارد.

:# A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

بعضی از نویسندگان این نوع دستور زبان را یک گرامر منظم راست (یا گرامر خطی از راست) و عبارت بالایی را یک گرامر منظم راست دقیق (یا گرامر خطی راست دقیق) می‌نامند.

:# A -> ε که A جزئی از N و ε جزئی از مجموعه تهی می‌باشد.

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

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