דקדוק חופשי-הקשר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הנדב הנכון (שיחה | תרומות) מאין תקציר עריכה |
יהונתן חרמץ (שיחה | תרומות) מ קישורים פנימיים |
||
שורה 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> הן [[מחרוזת (מדעי המחשב)|מחרוזות]] כלשהן של משתנים דקדוקיים וסימנים טרמינליים (ייתכן וריקות).
==הגדרה==
|