שפה חופשית הקשר

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

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

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

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

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

דוגמה

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

לעומת זאת, השפה ${\displaystyle \ L=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}}$ אינה חופשית הקשר, ניתן להוכיח זאת על נקלה באמצעות שימוש בלמת הניפוח לשפות חופשיות הקשר.

סגירות

משפחת השפות חופשיות ההקשר סגורה תחת מספר פעולות:

• הפעלת הומומורפיזם על מילות הקוד (התאמה השומרת על פעולת השרשור)
• שרשור שתי שפות זו לזו
• הפעלת סגור קלין על שפה
• איחוד שתי שפות
• חיתוך עם שפה רגולרית

לעומת זאת, משפחה זו אינה סגורה תחת הפעולות:

• השלמת שפה
• חיתוך עם שפה חופשית הקשר
• הפרש בין שתי שפות חופשיות הקשר

מיזמי קרן ויקימדיה
ספר לימוד בוויקיספר: אוטומטים ושפות פורמליות

בעיות הכרעה הקשורות לשפות חופשיות הקשר

מספר שאלות הקשורות לשפות חופשיות הקשר לא כריעות, בהן:

• שקילות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים שוות, כלומר ${\displaystyle L(A)=L(B)}$?
• זרות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים לא נחתכות, כלומר ${\displaystyle L(A)\cap L(B)=\phi }$?
• הכלה: נתונים שני דקדוקים A ו-B, האם שפה אחת מוכלת בשנייה, כלומר ${\displaystyle L(A)\subseteq L(B)}$?

הערה: כל הבעיות האלה כריעות כשמדובר בשפות רגולריות.

לעומת זאת השאלות הבאות כריעות:

• שפה ריקה: בהינתן דקדוק, האם השפה שהוא מגדיר ריקה?
• סופיות: בהינתן דקדוק, האם השפה שהוא מגדיר סופית?
• חברות בשפה: בהינתן דקדוק A ומחרוזת X האם X בשפה L(A)?

קישורים חיצוניים

• ספריית boost לשפות חופשיות הקשר בC++
• ספריית pyparsing לשפות חופשיות הקשר בפייתון (אורכב 08.02.2012 בארכיון Wayback Machine)