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

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

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

הגדרהעריכה

דקדוק תלוי הקשר   מוגדר על ידי הרביעייה  , כאשר:

  1.   - קבוצת משתנים
  2.   - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
  3.   - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים
     כך ש  ו  
  4.   - סימן ההתחלה. משתנה מתוך  .

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

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

 

הערות שולייםעריכה

  1. ^ Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, 2011-02-14, ISBN 978-1-4496-1552-9. (באנגלית)
  ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.