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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
Crystal Clear app help index.svg
ערך מחפש מקורות
רובו של ערך זה אינו כולל מקורות או הערות שוליים, וככל הנראה, הקיימים אינם מספקים.

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

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

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

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

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

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

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

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

ראו גם

P Computer-science.svg ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0