דקדוק חופשי-הקשר – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←לקריאה נוספת: כיווניות |
←דו-משמעות: הרחבה |
||
שורה 21:
צורה אחרת לדקודקים חסרי הקשר היא [[הצורה הנורמלית של גרייבך]], הקרויה על-שם [[מדען מחשב|מדענית המחשב]] [[שילה גרייבך]]. בדקדוק זה כל כלל יצירה הוא מהצורה <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>.}}. עבור שפות שאינן דו-משמעיות בצורה אינהרנטית, קיים דקדוק שאינו דו-משמעי, אך לא ידועה דרך סיסטמית להמיר דקדוק דו-משמעי לדקדוק שאינו דו-משמעי. נוסף על כך, השאלה האם דקדוק נתון הוא דו-משמעי או לאו אינה [[כריעות|כריעה]], כלומר לא קיים [[אלגוריתם]] שפותר אותה.
==ראו גם==
| |||