אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/דו-משמעות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
תרגיל |
||
שורה 3:
קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: <math>S\Rightarrow 0S1 \Rightarrow 0\epsilon1 = 01</math> אך גם <math>S\to 01</math>. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל <math>S\to 0S1 \mid \epsilon</math> יוצר את אותה השפה, ואינו דו-משמעי.
{{תרגיל|שאלה=האם הדקדוק הבא דו משמעי? אם כן, מצא דקדוק חלופי שאינו דו משמעי.
== דו משמעות אינהרנטית ==▼
<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>C\to 1C \mid \epsilon \qquad D\to 1D2 \mid \epsilon</math></center>
|פתרון=הדקדוק דו משמעי. המילה 02 יכולה להיווצר בשני אופני שונים. בראשון <math>S\Rightarrow A</math> ובשני <math>S\Rightarrow C</math>.{{ש}}
זו המילה היחידה שהינה דו משמעית. נשנה כך שלא ייתכן שתיווצר בצורה השניה על-ידי כך שנשנה את כללי הגזירה של המשתנה D ל-<math>D\to 1D2 \mid 12</math>.}}
▲== דו משמעות אינהרנטית ==
מחלקת השפות חופשיות ההקשר נחלקות לשתי תת-מחלקות:
# שפות שאינן דו-משמעיות
|