דקדוק חופשי-הקשר – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 1:
ב[[שפה פורמלית|שפות פורמליות]], '''דקדוק חופשי-הקשר''' (גם: דקדוק חסר הקשר) הוא [[דקדוק]] אשר כל כלל יצירה בו הוא מהצורה <math>\ A\to\alpha</math> כאשר <math>\ A</math> הוא משתנה דקדוקי ואילו <math>\ \alpha</math> היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דקדוק חסר הקשר יוצר [[שפה חסרת הקשר]] (טיפוס 2 ב[[ההיררכייה של חומסקי]]).
 
המונח "חסר הקשר" מציין כי כלל היצירה עבור <math>\ A</math> יכול להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של <math>\ A</math>, כלומר ללא חשיבות להקשר בו הוא מופיע. ב[[דקדודדקדוק תלוי הקשר]], לעומת זאת, ייתכנו כללי יצירה מהצורה <math>\ \alpha A\beta \to\alpha\gamma\beta</math>, כאשר <math>\ A</math> הוא משתנה דקדוקי ו<math>\ \alpha,\beta,\gamma</math> הן [[מחרוזת (מדעי המחשב)|מחרוזות]] כלשהן של משתנים דקדוקיים וסימנים טרמינליים (ייתכן וריקות).
 
==הגדרה==