דקדוק תלוי הקשר
קפיצה לניווט
קפיצה לחיפוש
ערך מחפש מקורות
| ||
ערך מחפש מקורות |
בשפות פורמליות, דקדוק תלוי-הקשר הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה כאשר Α ו B הן מחרוזת כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש. דקדוק חסר הקשר יוצר שפה תלוית הקשר (טיפוס 3 בהיררכיה של חומסקי).
המונח "תלוי הקשר" מציין כי כלל היצירה עבור A מתבצע עם חשיבות לשאלה מה נמצא מימינו ומשמאלו של A כלומר עם חשיבות להקשר בו הוא מופיע.
הגדרה
דקדוק חסר הקשר מוגדר על ידי הרביעייה , כאשר:
- - קבוצת משתנים
- - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
- - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים
כך ש ו - - סימן ההתחלה. משתנה מתוך .
אומרים שהדקדוק יוצר מילה , אם ניתן להתחיל מהמשתנה , ועל ידי ביצוע אחד או יותר מכללי היצירה שב-, להגיע אל המילה . מסמנים במקרה זה .
השפה הנוצרת על ידי הדקדוק , היא אוסף כל המחרוזות , אותן ניתן לייצר מ-, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,