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

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

כל דקדוק חסר הקשר לא ריק שאינו יוצר את המילה הריקה <math>\epsilon</math>, ניתן להמרה לדקדוק בו כל כלל יצירה הוא מהצורה <math>A\to BC</math> או <math>A\to a</math> כאשר <math>A,B,C</math> משתנים ו-<math>a</math> טרמינל. צורה זו נקראת [[הצורה הנורמלית של חומסקי]] על-שם ממציאה, ה[[בלשן]] [[נועם חומסקי]].

צורה נורמאלית אחרת הינהלדקודקים חסרי הקשר היא [[הצורה הנורמלית של גרייבך]], הקרויה על-שם [[מדען מחשב|מדענית המחשב]] [[שילה גרייבך]]. בדקדוק זה כל כלל יצירה הוא מהצורה <math>A\to a \alphaX</math>, כאשר <math>a</math> הינו טרמינל, ו-<math>\alphaX</math> הוא רצף של אפס או יותר משתנים. לצורה זו כמה תכונות מעניינות, שכן כל כלל יצירה מוסיף בדיוק אות אחת למילה נוצרת, ולכן אורך המילה נתון על-ידי כמות כללי היצירה שהופעלו. כמו כן, ניתן להמיר כל דקדוק מצורת גרייבך ל[[אוטומט מחסנית]] שאין בו מעברי-<math>\epsilon</math>, ובכך להראות כי תמיד ניתן לבטל מעברי-<math>\epsilon</math> באוטומטי מחסנית.

* [[שפותשפה רגולריותרגולרית]]