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

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

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

 הגדרה פורמלית 
מבחינה פורמלית נהוג להגדיר שפה תלוית הקשר כשפה שנוצרת על ידי דקדוק תלוי הקשר (דקדוק מטיפוס 3 בהיררכיה של חומסקי). דקדוק G ייקרא תלוי הקשר אם ורק אם כל כלל יצירה בו הוא מהצורה  כאשר A ו-B הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך שמתקיים .

המונח "תלוית הקשר" בא מכך שההחלפה של A צריכה להתבצע עם חשיבות לשאלה מה נמצא מימינו ומשמאלו של משתנה דקדוקי ב-A, כלומר עם חשיבות להקשר בו הוא מופיע.

 ראו גם 
 שפה חופשית הקשר

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