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

מתוך ויקיפדיה, האנציקלופדיה החופשית

בשפות פורמליות, דקדוק תלוי-הקשר[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. (באנגלית)
Crystal Clear app ktalkd.png ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.