פתיחת התפריט הראשי

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

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

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

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

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

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

ראו גםעריכה

  ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.