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

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

گرامر G به صورت یک چهارتایی به شکل $G=(V\,,T\,,S\,,P\,)$ تعریف می‌شود که در آن:

• V مجموعه‌ای متناهی از اشیاء است که متغیر نامیده می‌شوند.
• T مجموعه‌ای متناهی از اشیاء است که پایانه نامیده می‌شوند.
• $S\in V$ یک نماد خاص است که متغیر شروع نامیده می‌شود.
• 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 که شامل متغیرها و پایانه‌ها هستند فرم‌های جمله ای اشتقاق می‌گویند.