דקדוק תלוי-הקשר

תבנית:מקורות בשפות פורמליות, דקדוק תלוי-הקשר הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה $\mathrm{A}\to \mathrm{B}$ כאשר Α ו B הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש$|\mathrm{A}|\le |\mathrm{B}|$. דקדוק תלוי הקשר יוצר שפה תלוית הקשר (טיפוס 3 בהיררכיה של חומסקי).

המונח "תלוי הקשר" מציין כי כלל היצירה עבור A מתבצע עם חשיבות לשאלה מה נמצא מימינו ומשמאלו של A כלומר עם חשיבות להקשר בו הוא מופיע.

הגדרה

דקדוק תלוי הקשר $G$ מוגדר על ידי הרביעייה $G=(V,\mathrm{\Sigma },R,S)$, כאשר:

1. $V$ - קבוצת משתנים
2. $\mathrm{\Sigma }$ - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
3. $R$ - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים $$(A\to B)\in R$$כך ש $|\mathrm{A}|\le |\mathrm{B}|$ו $\mathrm{A},\mathrm{B}\in (V\cup \mathrm{\Sigma }{)}^{*}$
4. $S$ - סימן ההתחלה. משתנה מתוך $V$.

אומרים שהדקדוק $G$ יוצר מילה $x$, אם ניתן להתחיל מהמשתנה $S$, ועל ידי ביצוע אחד או יותר מכללי היצירה שב-$R$, להגיע אל המילה $x\in {\mathrm{\Sigma }}^{*}$. מסמנים במקרה זה $S{\Rightarrow }^{*}x$.

השפה הנוצרת על ידי הדקדוק $G$, היא אוסף כל המחרוזות $x$, אותן ניתן לייצר מ-$S$, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי, $$L(G)=\{x\mid S{\Rightarrow }^{*}x\}$$