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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בשפות פורמליות, דקדוק חופשי-הקשר (גם: דקדוק חסר הקשר) הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה \ 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\}

צורה נורמלית[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – הצורה הנורמלית של חומסקי

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

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

דו-משמעות[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ דוגמה לשפה דו-משמעית בצורה אינהרנטית היא השפה L=\{a^nb^nc^md^m\mid n,m \ge1\} \cup \{a^nb^mc^md^n\mid n,m\ge1\}.