דקדוק תלוי-הקשר
(הופנה מהדף דקדוק תלוי הקשר)
ערך מחפש מקורות | |
בשפות פורמליות, דקדוק תלוי-הקשר[1] הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה כאשר Α ו B הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש. דקדוק תלוי הקשר יוצר שפה תלוית הקשר (טיפוס 3 בהיררכיה של חומסקי).
המונח "תלוי הקשר" מציין כי כלל היצירה עבור A מתבצע עם חשיבות לשאלה מה נמצא מימינו ומשמאלו של A כלומר עם חשיבות להקשר בו הוא מופיע.
הגדרה
עריכהדקדוק תלוי הקשר מוגדר על ידי הרביעייה , כאשר:
- - קבוצת משתנים
- - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
- - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים כך ש ו
- - סימן ההתחלה. משתנה מתוך .
אומרים שהדקדוק יוצר מילה , אם ניתן להתחיל מהמשתנה , ועל ידי ביצוע אחד או יותר מכללי היצירה שב- , להגיע אל המילה . מסמנים במקרה זה .
השפה הנוצרת על ידי הדקדוק , היא אוסף כל המחרוזות , אותן ניתן לייצר מ- , על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,
הערות שוליים
עריכה- ^ Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, 2011-02-14, ISBN 978-1-4496-1552-9. (באנגלית)