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

در علم کامپیوتر نظری و تئوری زبان رسمی، گرامر پیشوندی نوعی از سیستم بازنویسی رشته است که شامل مجموعه‌ای از قوانین بازنویسی رشته می‌باشد که شبیه به دستور زبان رسمی یا یک سیستم 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 است.

مثال

دستور زبان پیشوندی زیر
 {Σ = {۰, ۱
 {S = {۰۱, ۱۰
 {P = {۰ → ۰۱۰, ۱۰ → ۱۰۰

زبان تعریف شده توسط عبارت منظم روبه رو را توصیف می‌کند :

جستارهای وابسته

منابع 

 ویکی‌پدیای انگلیسی
زبان‌های صوری
قاعده‌ها
ویکی‌سازی رباتیک