דקדוק תלוי-הקשר

בשפות פורמליות, דקדוק תלוי-הקשר הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה $ \mathrm {A} \rightarrow \mathrm {B} $ כאשר Α ו B הן מחרוזת כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש$ |\mathrm {A} |\leq |\mathrm {B} | $. דקדוק חסר הקשר יוצר שפה תלוית הקשר (טיפוס 3 בהיררכיה של חומסקי).

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

הגדרה

דקדוק חסר הקשר $ G $ מוגדר על ידי הרביעייה $ G=(V,\Sigma ,R,S) $, כאשר:

1. $ V $ - קבוצת משתנים
2. $ \Sigma $ - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
3. $ R $ - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים $ (A\to \ B)\in R $כך ש $ |\mathrm {A} |\leq |\mathrm {B} | $ו $ \mathrm {A} ,\mathrm {B} \in (V\cup \Sigma )^{*} $
4. $ S $ - סימן ההתחלה. משתנה מתוך $ V $.

אומרים שהדקדוק $ G $ יוצר מילה $ x $, אם ניתן להתחיל מהמשתנה $ S $, ועל ידי ביצוע אחד או יותר מכללי היצירה שב-$ R $, להגיע אל המילה $ x\in \Sigma ^{*} $. מסמנים במקרה זה $ S\Rightarrow ^{*}x $.

השפה הנוצרת על ידי הדקדוק $ G $, היא אוסף כל המחרוזות $ x $, אותן ניתן לייצר מ-$ S $, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,

$ L(G)=\{x\mid S\Rightarrow ^{*}x\} $

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] דקדוק תלוי-הקשר25717334