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

בשפות פורמליות, דקדוק תלוי-הקשר הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה  כאשר Α ו B הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש. דקדוק תלוי הקשר יוצר שפה תלוית הקשר (טיפוס 3 בהיררכיה של חומסקי).

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

הגדרה
דקדוק תלוי הקשר  מוגדר על ידי הרביעייה , כאשר:
  - קבוצת משתנים
  - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
  - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים כך ש ו 
  - סימן ההתחלה. משתנה מתוך .

אומרים שהדקדוק  יוצר מילה , אם ניתן להתחיל מהמשתנה , ועל ידי ביצוע אחד או יותר מכללי היצירה שב-, להגיע אל המילה . מסמנים במקרה זה .

השפה הנוצרת על ידי הדקדוק , היא אוסף כל המחרוזות , אותן ניתן לייצר מ-, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,

הערות שוליים

שפות פורמליות