گرامر (زبان‌های صوری)

تعریف صوری گرامر

گرامر G به صورت یک چهارتایی به شکل تعریف می‌شود که در آن:

  • V مجموعه‌ای متناهی از اشیاء است که متغیر نامیده می‌شوند.
  • T مجموعه‌ای متناهی از اشیاء است که پایانه نامیده می‌شوند.
  • یک نماد خاص است که متغیر شروع نامیده می‌شود.
  • P مجموعه متناهی از قانون‌های تولید نامیده می‌شود.

فرض می‌کنیم مجموعه‌های V و T دو مجموعه غیر تهی و مجزا هستند.

منابع

  • سلیمی، بابک و پورمحقق، مجتبی. نظریه زبان‌ها و ماشین‌ها، چاپ دوم، مشهد:نما، جهان فردا، ۱۳۸۸

گرامر (G=(V,T,S,P را در نظر بگیرید. مجموعه ی{L(G)={w € T* : S =*> W زبان تعریف شده توسط G است. اگر(W € L(G باشد، آنگاه توالی S=> w1 =>w2 => ... =>wn => w را یک اشتقاق از رشته w می‌گویند. به رشته‌های S, w1,w2,...,wn که شامل متغیرها و پایانه‌ها هستند فرم‌های جمله ای اشتقاق می‌گویند.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.