לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

נאמר שדקדוק הוא דו-משמעי (לעתים גם: רב-משמעי, ambiguous) אם קיימת בשפה הנוצרת על-ידי הדקדוק מילה, שניתן ליצור אותה בשני אופנים שונים. כלומר, אם קיימים שני עצי-גזירה שונים עבור אותה המילה. דוגמא לדקדוק דו-משמעי הוא הדקדוק הבא

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


דוגמא נוספת: הדקדוק הינו דו-משמעי. להלן שני עצי יצירה עבור המילה :

מאידך, הדקדוק יוצר את אותה שפה (), ואינו דו משמעי.

עץ היצירה היחיד של המילה aaa בדקדוק שאינו דו-משמעי



דו משמעות אינהרנטית[עריכה]

מחלקת השפות חופשיות ההקשר נחלקות לשתי תת-מחלקות:

  1. שפות שאינן דו-משמעיות
  2. שפות דו-משמעיות באופן אינהרנטי

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

מילים מהצורה תמיד יהיו בעלי שני עצי גזירה שונים, אחד עקב הכללים שמייצרים את והשני עקב הכללים שמייצרים את עבור .


פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.



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

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

(זהו נושא מתקדם השייך לקורס תורת החישוביות)


הפרק הקודם:
צורות נורמליות לדקדוקים חסרי הקשר
דו-משמעות -