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

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

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

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

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

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

ראו גם[עריכת קוד מקור | עריכה]

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