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

{{אוטומטים ושפות פורמליות}}
נאמר שדקדוק הוא '''דו-משמעי''' (לעתים גם: רב-משמעי, ambiguous) אם קיימת בשפה הנוצרת על-ידי הדקדוק מילה, שניתן ליצור אותה בשני אופנים שונים. כלומר, אם קיימים שני עצי-גזירה שונים עבור אותה המילה. דוגמא לדקדוק דו-משמעי הוא הדקדוק הבא
<center><math>S\to 0S1 \mid \varepsilon \mid 01</math></center> 
קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: <math>S\Rightarrow 0S1 \Rightarrow 0\varepsilon1 = 01</math> אך גם <math>S\Rightarrow 01</math>. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל <math>S\to 0S1 \mid \varepsilon</math> יוצר את אותה השפה, ואינו דו-משמעי.


דוגמא נוספת: הדקדוק <math>S\to SS \mid a</math> הינו דו-משמעי. להלן שני עצי יצירה עבור המילה <math>aaa</math>:
<gallery>
קובץ:Tree aaa 1.svg|עץ יצירה 1 למילה aaa
קובץ:Tree aaa 2.svg|עץ יצירה 2 למילה aaa
</gallery>
מאידך, הדקדוק <math>S\to aS \mid \varepsilon</math> יוצר את אותה שפה (<math>aa^*</math>), ואינו דו משמעי.
[[קובץ:Tree aaa right.svg|80px|ממוסגר|ימין|עץ היצירה היחיד של המילה aaa בדקדוק שאינו דו-משמעי]]

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

== דו משמעות אינהרנטית ==
מחלקת השפות חופשיות ההקשר נחלקות לשתי תת-מחלקות:
# שפות שאינן דו-משמעיות
# שפות דו-משמעיות באופן אינהרנטי

לכל שפה במחלקה הראשונה, ניתן למצוא דקדוק שאינו דו משמעי. עם זאת, שפות במחלקה השנייה בנויות באופן שהן חייבות להיות דו משמעיות, וכל דקדוק שיוצר אותן יהיה דו משמעי. דוגמא לשפה דו-משמעית באופן אינהרנטי היא השפה
<center><math>L=\{a^nb^nc^md^m\mid n,m \ge1\} \cup \{a^nb^mc^md^n\mid n,m\ge1\}</math></center>
מילים מהצורה <math>a^nb^nc^nd^n</math> תמיד יהיו בעלי שני עצי גזירה שונים, אחד עקב הכללים שמייצרים את <math>a^nb^nc^md^m</math> והשני עקב הכללים שמייצרים את <math>a^nb^mc^md^n</math> עבור <math>n=m</math>.
{{להשלים|הוכחה}}

== כריעות בעיית הדו-משמעות==
בהנתן דקדוק חסר-הקשר דו-משמעי, לא קיים אלגוריתם הממיר אותו לדקדוק לא דו-משמעי (אם קיים). יתר על כן, עצם השאלה האם דקדוק מסויים הוא דו-משמעי או לא, אינו בעיה כריעה - כלומר לא קיים אלגוריתם (מכונת טיורינג) המכריע את השפה 
<center><math>L = \{ G \mid G \text{ is unambiguous grammar}\}</math></center>
(זהו נושא מתקדם השייך לקורס [[תורת החישוביות]])

{{אוטומטים ושפות פורמליות|מוגבל}}

[[קטגוריה:אוטומטים ושפות פורמליות|אוטומט מחסנית]]