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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

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

  • Σ یک الفبای متناهی است.
  • S مجموعه‌ای متناهی از رشته‌های بیس روی Σ است.
  • P مجموعه‌ای از قواعد تولید به فرم uv است که 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 = {۰ → ۰۱۰, ۱۰ → ۱۰۰

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]