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

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

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

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

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

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

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

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

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

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

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

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

$L=\{a^n{b}^n{c}^m{d}^m\mid n,m\ge 1\}\cup \{a^n{b}^m{c}^m{d}^n\mid n,m\ge 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}\}$

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