במדעי המחשב, שפה חופשית הקשר (או שפה חסרת הקשר) הינה שפה פורמלית אשר קיים דקדוק המגדיר אותה; כלומר, שפה $\backslash \; L$ היא שפה חופשית הקשר אם קיים דקדוק $\backslash \; G$ כך ש-$\backslash \; L$ היא אוסף כל המילים שניתן לגזור מהסימן התחילי של $\backslash \; G$. ניתן להוכיח, ששפה היא חופשית הקשר אם ורק אם קיים אוטומט מחסנית לא דטרמניסטי המקבל אותה.

משפחת השפות חופשיות ההקשר סגורה תחת פעולות של איחוד ושרשור שפות, אך לא תחת חיתוך והפרש (להבדיל מהשפות הרגולריות).

הגדרה פורמלית

---

מבחינה פורמלית נהוג להגדיר שפה חופשית הקשר כשפה שנוצרת על ידי דקדוק חופשי הקשר (דקדוק מטיפוס 2 בהיררכייה של חומסקי). דקדוק $\backslash \; G$ ייקרא חופשי הקשר אם ורק אם כל כלל יצירה בו הוא מהצורה $\backslash \; A\backslash to\backslash alpha$ כאשר $\backslash \; A$ הוא משתנה דקדוקי ואילו $\backslash \; \backslash alpha$ היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים.

המונח "חופשית הקשר" בא מכך שההחלפה של $\backslash \; A$ יכולה להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של $\backslash \; A$, כלומר ללא חשיבות להקשר בו הוא מופיע.

דוגמה

---

השפה $\backslash \; L=\backslash left\backslash \{a^nb^n|n\backslash ge\; 1\backslash right\backslash \}$ היא שפה חופשית הקשר ואינה שפה רגולרית. דקדוק חופשי הקשר שיוצר אותה הוא הדקדוק שמכיל את המשתנה $\backslash \; S$ והסימנים הטרמינליים $\backslash \; a,b$ ואת כלל היצירה $\backslash \; S\backslash to\; aSb|ab$.

לעומת זאת, השפה $\backslash \; L=\backslash left\backslash \{a^nb^nc^n|n\backslash ge\; 1\backslash right\backslash \}$ אינה חופשית הקשר, ניתן להוכיח זאת על נקלה באמצעות שימוש בלמת בר הלל.

חישוביות

Context-free language | Bezkontextový jazyk | Kontextfreie Sprache | Yhteydetön kieli | Linguaggio context-free | Język bezkontekstowy | Limbaje independente de context