Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
שפה תלוית הקשר היא שפה פורמלית אשר קיים דקדוק תלוי הקשר המגדיר אותה; כלומר, שפה L היא שפה תלוית הקשר אם קיים דקדוק תלוי הקשר G כך ש-L היא אוסף כל המילים שניתן לגזור מהסימן התחילי של G. ניתן להוכיח, ששפה היא תלוית הקשר אם קיימת מכונת טיורינג חסומה ליניארית המקבלת אותה.
ערך מחפש מקורות | |
משפחת השפות תלויות ההקשר סגורה תחת פעולות של איחוד, שרשור, כוכב קלין, חיתוך ומשלים.
מבחינה פורמלית נהוג להגדיר שפה תלוית הקשר כשפה שנוצרת על ידי דקדוק תלוי הקשר (דקדוק מטיפוס 3 בהיררכיה של חומסקי). דקדוק G ייקרא תלוי הקשר אם ורק אם כל כלל יצירה בו הוא מהצורה כאשר A ו-B הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך שמתקיים .
המונח "תלוית הקשר" בא מכך שההחלפה של A צריכה להתבצע עם חשיבות לשאלה מה נמצא מימינו ומשמאלו של משתנה דקדוקי ב-A, כלומר עם חשיבות להקשר בו הוא מופיע.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.