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

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

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

הגדרה

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

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

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

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

הערות שוליים

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.