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

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

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

הגדרה

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

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

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

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

הערות שוליים

^ Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, 2011-02-14, ISBN 978-1-4496-1552-9. (באנגלית)

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

[1] Peter Linz, An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers, 2011-02-14, ISBN 978-1-4496-1552-9. (באנגלית)

[1]

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