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

ב[[שפה פורמלית|שפות פורמליות]], '''דקדוק חופשי-הקשר''' (גם: '''דקדוק חסר-הקשר''') הוא [[דקדוק]] אשר כל כלל יצירה בו הוא מהצורה <math>\ A\to\alpha</math> כאשר <math>\ A</math> הוא משתנה דקדוקי ואילו <math>\ \alpha</math>היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דקדוק חסר הקשר יוצר [[שפה חופשית הקשר]] (טיפוס 2 ב[[ההיררכיה של חומסקי|היררכיה של חומסקי]]).

המונח "חסר הקשר" מציין כי כלל היצירה עבור  <math>\ A</math> יכול להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של <math>\ A</math>, כלומר ללא חשיבות להקשר בו הוא מופיע. ב[[דקדוק תלוי הקשר]], לעומת זאת, ייתכנו כללי יצירה מהצורה <math>\ \alpha A\beta \to\alpha\gamma\beta</math>, כאשר <math>\ A</math> הוא משתנה דקדוקי ו<math>\ \alpha,\beta,\gamma</math> הן [[מחרוזת (מדעי המחשב)|מחרוזות]] כלשהן של משתנים דקדוקיים וסימנים טרמינליים (ייתכן וריקות).

==הגדרה==
דקדוק חסר הקשר <math>G</math> מוגדר על ידי הרביעייה <math>G=(V,\Sigma, R, S)</math>, כאשר:
# <math>V</math> - קבוצת משתנים
# <math>\Sigma</math> - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את ה[[אלפבית (שפה פורמלית)|אלפבית]] של השפה הנוצרת.
# <math>R</math> - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים<math display="block">(A\to\alpha)\in R \qquad A\in V, \alpha\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>

== צורה נורמלית==
{{ערך מורחב|הצורה הנורמלית של חומסקי}}
כל דקדוק חסר הקשר לא ריק שאינו יוצר את המילה הריקה <math>\epsilon</math>, ניתן להמרה לדקדוק בו כל כלל יצירה הוא מהצורה <math>A\to BC</math> או <math>A\to a</math> כאשר <math>A,B,C</math> משתנים ו-<math>a</math> טרמינל. צורה זו נקראת [[הצורה הנורמלית של חומסקי]] על-שם ה[[בלשן]] [[נועם חומסקי]].

צורה אחרת לדקדוקים חסרי הקשר  היא [[הצורה הנורמלית של גרייבך]], הקרויה על-שם [[מדען מחשב|מדענית המחשב]] [[שילה גרייבך]]. בדקדוק זה כל כלל יצירה הוא מהצורה <math>A\to a X</math>, כאשר <math>a</math> הוא טרמינל, ו-<math>X</math> הוא רצף של אפס או יותר משתנים. לצורה זו כמה תכונות מעניינות, שכן כל כלל יצירה מוסיף בדיוק אות אחת למילה נוצרת, ולכן אורך המילה נתון על ידי כמות כללי היצירה שהופעלו. כמו כן, ניתן להמיר כל דקדוק מצורת גרייבך ל[[אוטומט מחסנית]] שאין בו מעברי-<math>\epsilon</math>, ובכך להראות כי תמיד ניתן לבטל מעברי-<math>\epsilon</math> באוטומטי מחסנית.

==דו-משמעות==
אם עבור דקדוק נתון קיימות שתי דרכים שונות ליצור מילה מסוימת, אומרים שהדקדוק [[דו-משמעות|דו-משמעי]]. לתכונה זה משמעויות בבלשנות וב[[קומפילציה]]. קיימות שפות חסרות הקשר שהן דו-משמעויות בצורה אינהרנטית - כל דקדוק היוצר אותן יהיה דו משמעי{{הערה|1=דוגמה לשפה דו-משמעית בצורה אינהרנטית היא השפה <math>L=\{a^nb^nc^md^m\mid n,m \ge1\} \cup \{a^nb^mc^md^n\mid n,m\ge1\}</math>.}}. עבור שפות שאינן דו-משמעיות בצורה אינהרנטית, קיים דקדוק שאינו דו-משמעי, אך לא ידועה דרך סיסטמית להמיר דקדוק דו-משמעי לדקדוק שאינו דו-משמעי. נוסף על כך, השאלה האם דקדוק נתון הוא דו-משמעי או לאו אינה [[כריעות|כריעה]], כלומר לא קיים [[אלגוריתם]] שפותר אותה.

==ראו גם==
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}
* [[עמימות#דו-משמעות תחבירית|דו-משמעות תחבירית]]
* [[שפה רגולרית]]
* [[ההיררכיה של חומסקי]]
* [[תורת האוטומטים - מונחים]]

==לקריאה נוספת==
* {{פא"ר|מספר=419|שם הספר=אוטומטים ושפות פורמליות ב|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}}
<div class="mw-content-ltr">
* John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. ''Introduction to Automata Theory, Languages, and Computation'', 3rd Edition, Addison-Wesley, 2006. {{ISBN|0-321-45536-3}}.
* John E. Hopcroft and Jeffrey D. Ullman, ''Introduction to Automata Theory, Languages and Computation'', Addison-Wesley Publishing, Reading Massachusetts, 1979. {{ISBN|0-201-02988-X}}. 
</div>

==קישורים חיצוניים==
* {{לא מדויק|2015/03/05/context_free_grammars_intro|מבוא לדקדוקים חסרי הקשר}}

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

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

[[קטגוריה:שפות פורמליות]]