דקדוק חופשי-הקשר

בשפות פורמליות, דקדוק חופשי-הקשר (גם: דקדוק חסר הקשר) הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה $\ A\to \alpha$ כאשר $\ A$ הוא משתנה דקדוקי ואילו $\ \alpha$היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דקדוק חסר הקשר יוצר שפה חופשית הקשר (טיפוס 2 בהיררכיה של חומסקי).

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

הגדרה

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

1. $V$ - קבוצת משתנים
2. $\Sigma$ - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
3. $R$ - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים
   $$(A\to \alpha )\in R\qquad A\in V,\alpha \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\}$$

צורה נורמלית

ערך מורחב – הצורה הנורמלית של חומסקי

כל דקדוק חסר הקשר לא ריק שאינו יוצר את המילה הריקה $\epsilon$, ניתן להמרה לדקדוק בו כל כלל יצירה הוא מהצורה $A\to BC$ או $A\to a$ כאשר $A,B,C$ משתנים ו-$a$ טרמינל. צורה זו נקראת הצורה הנורמלית של חומסקי על-שם הבלשן נועם חומסקי.

צורה אחרת לדקדוקים חסרי הקשר היא הצורה הנורמלית של גרייבך, הקרויה על-שם מדענית המחשב שילה גרייבך. בדקדוק זה כל כלל יצירה הוא מהצורה $A\to aX$, כאשר $a$ הוא טרמינל, ו-$X$ הוא רצף של אפס או יותר משתנים. לצורה זו כמה תכונות מעניינות, שכן כל כלל יצירה מוסיף בדיוק אות אחת למילה נוצרת, ולכן אורך המילה נתון על ידי כמות כללי היצירה שהופעלו. כמו כן, ניתן להמיר כל דקדוק מצורת גרייבך לאוטומט מחסנית שאין בו מעברי-$\epsilon$, ובכך להראות כי תמיד ניתן לבטל מעברי-$\epsilon$ באוטומטי מחסנית.

דו-משמעות

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

ראו גם

• דו-משמעות תחבירית
• שפה רגולרית
• ההיררכיה של חומסקי
• תורת האוטומטים - מונחים

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000

• 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.

קישורים חיצוניים

• גדי אלכסנדרוביץ', מבוא לדקדוקים חסרי הקשר, באתר "לא מדויק", 5 במרץ 2015