הצגת המקור של הדף "דקדוק תלוי-הקשר"

{{מקורות|רמה=מחפש|נושא=מדעי הרוח|נושא2=מחשוב}}
ב[[שפה פורמלית|שפות פורמליות]], '''דקדוק תלוי-הקשר<ref>{{צ-ספר|שם=An Introduction to Formal Languages and Automata|קישור=https://books.google.co.il/books?id=hsxDiWvVdBcC&pg=PA291&redir_esc=y#v=onepage&q&f=false|מו"ל=Jones & Bartlett Publishers|שנת הוצאה=2011-02-14|ISBN=978-1-4496-1552-9|מחבר=Peter Linz|שפה=en}}</ref>''' הוא [[דקדוק]] אשר כל כלל יצירה בו הוא מהצורה <math>\Alpha\rightarrow\Beta</math> כאשר '''''Α''''' ו '''''B''''' הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים כך ש<math>|\Alpha|\leq|\Beta|</math>. דקדוק תלוי הקשר יוצר [[שפה תלוית הקשר]] (טיפוס 3 ב[[ההיררכיה של חומסקי|היררכיה של חומסקי]]).

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

==הגדרה==
דקדוק תלוי הקשר <math>G</math> מוגדר על ידי הרביעייה <math>G=(V,\Sigma, R, S)</math>, כאשר:
# <math>V</math> - קבוצת משתנים
# <math>\Sigma</math> - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את ה[[אלפבית]] של השפה הנוצרת.
# <math>R</math> - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים <math display="block">(A\to\ B)\in R</math>כך ש <math>|\Alpha|\leq|\Beta|</math>ו <math>\Alpha ,\Beta \in (V \cup \Sigma)^*</math>
# <math>S</math> - סימן ההתחלה. משתנה מתוך <math>V</math>.

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

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

==הערות שוליים==
{{הערות שוליים}}

{{בקרת זהויות}}

{{קצרמר|מחשבים}}
[[קטגוריה:שפות פורמליות]]