گرامر پیشوندی

در علم کامپیوتر نظری و تئوری زبان رسمی، گرامر پیشوندی نوعی از سیستم بازنویسی رشته است که شامل مجموعه‌ای از قوانین بازنویسی رشته می‌باشد که شبیه به دستور زبان رسمی یا یک سیستم Semi-Thue است.

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

گرامرهای پیشوندی همهٔ زبان‌های منظم را شامل می‌شوند.

تعریف رسمی[ویرایش]

دستور زبان پیشوندی G یک سه تایی به شکل (Σ, S, P) است که در آن

Σ یک الفبای متناهی است.
S مجموعه‌ای متناهی از رشته‌های بیس روی Σ است.
P مجموعه‌ای از قواعد تولید به فرم u → v است که u و v رشته‌هایی رو Σ است.

برای رشته‌های X و Y می‌نویسم x →_G y ( بخوانید G نتیجه می‌گیرد y را از x در یک مرحله ) اگر رشته‌های u, v, w وجود داشته باشند به طوری که x = vu , y = wu و v → w در P .

توجه کنید که →_G یک رابطهٔ دوتایی روی رشته‌هایی از Σ ست.

زبان G که به صورت (L(G نشان داده می‌شود ، مجموعه‌ای از رشته‌های استخراج شده از S در صفر یا چند مرحله است : به طور رسمی مجموعه‌ای از رشته‌های w به طوریکه برای بعضی از s‌ ها در S و s R w که R بسته شدن انتقالی از →_G است.