گرامر پیشوندی
در علم کامپیوتر نظری و تئوری زبان رسمی، گرامر پیشوندی نوعی از سیستم بازنویسی رشته است که شامل مجموعهای از قوانین بازنویسی رشته میباشد که شبیه به دستور زبان رسمی یا یک سیستم 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 = {۰ → ۰۱۰, ۱۰ → ۱۰۰
زبان تعریف شده توسط عبارت منظم روبه رو را توصیف میکند :