הצגת המקור של הדף "שפה חופשית הקשר"

ב[[מדעי המחשב]], '''שפה חופשית הקשר''' (או '''שפה חסרת הקשר''') היא [[שפה פורמלית]] אשר קיים [[דקדוק חסר הקשר]] המגדיר אותה; כלומר, שפה <math>\ L</math> היא שפה חופשית הקשר אם קיים דקדוק חסר הקשר <math>\ G</math> כך ש-<math>\ L</math> היא אוסף כל המילים שניתן לגזור מהסימן התחילי של <math>\ G</math>. ניתן להוכיח, ששפה היא חופשית הקשר [[אם ורק אם]] קיים [[אוטומט מחסנית]] לא דטרמניסטי המקבל אותה.

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

==הגדרה פורמלית==
מבחינה פורמלית נהוג להגדיר שפה חופשית הקשר כשפה שנוצרת על ידי [[דקדוק חופשי הקשר]] (דקדוק מטיפוס 2 ב[[ההיררכיה של חומסקי|היררכיה של חומסקי]]). דקדוק <math>\ G</math> ייקרא חופשי הקשר אם ורק אם כל כלל יצירה בו הוא מהצורה <math>\ A\to\alpha</math> כאשר <math>\ A</math> הוא משתנה דקדוקי ואילו <math>\ \alpha</math> היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים.

המונח "חופשית הקשר" בא מכך שההחלפה של <math>\ A</math> צריכה להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של <math>\ A</math>, כלומר ללא חשיבות להקשר בו הוא מופיע.

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

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

== סגירות ==
משפחת השפות חופשיות ההקשר סגורה תחת מספר פעולות:
* הפעלת '''[[הומומורפיזם]]''' על מילות הקוד (התאמה השומרת על פעולת השרשור)
* '''שרשור''' שתי שפות זו לזו
* הפעלת '''[[סגור קלין]]''' על שפה
* '''[[איחוד (מתמטיקה)|איחוד]]''' שתי שפות
* '''חיתוך''' עם [[שפה רגולרית]]

לעומת זאת, משפחה זו אינה סגורה תחת הפעולות:
* [[משלים (מתמטיקה)|השלמת]] שפה
* [[חיתוך (מתמטיקה)|חיתוך]] עם שפה חופשית הקשר
* [[הפרש (תורת הקבוצות)|הפרש]] בין שתי שפות חופשיות הקשר
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}

==בעיות הכרעה הקשורות לשפות חופשיות הקשר==
מספר שאלות הקשורות לשפות חופשיות הקשר לא [[כריעות]], בהן:
*שקילות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים שוות, כלומר <math>L(A)=L(B)</math>?
* זרות: נתונים שני דקדוקים A ו-B, האם שתי השפות שהם מגדירים לא נחתכות, כלומר <math>L(A)\cap L(B) = \phi</math>? 
*הכלה: נתונים שני דקדוקים A ו-B, האם שפה אחת מוכלת בשנייה, כלומר <math>L(A)\subseteq L(B)</math>?
הערה: כל הבעיות האלה כריעות כשמדובר בשפות רגולריות. 

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

== קישורים חיצוניים ==
*[http://boost-spirit.com/home/ ספריית boost לשפות חופשיות הקשר בC++]
*[http://pyparsing.wikispaces.com/ ספריית pyparsing לשפות חופשיות הקשר בפייתון] {{Webarchive|url=https://web.archive.org/web/20120208161510/http://pyparsing.wikispaces.com/ |date=2012-02-08 }}

{{בקרת זהויות}}

[[קטגוריה:שפות פורמליות]]