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

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

$S\to 0S1\mid \varepsilon \mid 01$

קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: $S\Rightarrow 0S1\Rightarrow 0\varepsilon 1=01$ אך גם $S\Rightarrow 01$. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל $S\to 0S1\mid \varepsilon$ יוצר את אותה השפה, ואינו דו-משמעי.

דוגמא נוספת: הדקדוק $S\to SS\mid a$ הינו דו-משמעי. להלן שני עצי יצירה עבור המילה $aaa$:

• 
  עץ יצירה 1 למילה aaa
• 
  עץ יצירה 2 למילה aaa

מאידך, הדקדוק $S\to aS\mid \varepsilon$ יוצר את אותה שפה ($aa^{*}$), ואינו דו משמעי.

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

תרגיל : האם הדקדוק הבא דו משמעי? אם כן, מצא דקדוק חלופי שאינו דו משמעי. $S\to A\mid C$ $A\to 0A2\mid B\qquad C\to 0C2\mid D$ $B\to 1C\mid \varepsilon \qquad D\to 1D2\mid \varepsilon$
הדקדוק דו משמעי. המילה 02 יכולה להיווצר בשני אופני שונים. בראשון $S\Rightarrow A$ ובשני $S\Rightarrow C$. מילה זו והמילה הריקה הינן היחידות שהינן דו משמעיות. נשנה כך שלא ייתכן שתיווצרנה בצורה השניה על-ידי כך שנשנה את כללי הגזירה של המשתנה D ל-$D\to 1D2\mid 12$.

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

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

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

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

$L=\{a^{n}b^{n}c^{m}d^{m}\mid n,m\geq 1\}\cup \{a^{n}b^{m}c^{m}d^{n}\mid n,m\geq 1\}$

מילים מהצורה $a^{n}b^{n}c^{n}d^{n}$ תמיד יהיו בעלי שני עצי גזירה שונים, אחד עקב הכללים שמייצרים את $a^{n}b^{n}c^{m}d^{m}$ והשני עקב הכללים שמייצרים את $a^{n}b^{m}c^{m}d^{n}$ עבור $n=m$.

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

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

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

$L=\{G\mid G{\text{ is unambiguous grammar}}\}$

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

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

דו-משמעות

-