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

מתוך ויקיפדיה, האנציקלופדיה החופשית
Crystal Clear app help index.svg
ערך מחפש מקורות
רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים.

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

בשפות פורמליות, דקדוק תלוי-הקשר[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 ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.