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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ תבניות, קט
Gran (שיחה | תרומות)
מ עוד דוגמא
שורה 3:
<center><math>S\to 0S1 \mid \epsilon \mid 01</math></center>
קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: <math>S\Rightarrow 0S1 \Rightarrow 0\epsilon1 = 01</math> אך גם <math>S\Rightarrow 01</math>. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל <math>S\to 0S1 \mid \epsilon</math> יוצר את אותה השפה, ואינו דו-משמעי.
 
 
דוגמא נוספת: הדקדוק <math>S\to SS \mid a</math> הינו דו-משמעי. להלן שני עצי יצירה עבור המילה <math>aaa</math>:
<gallery>
קובץ:Tree aaa 1.svg|עץ יצירה 1 למילה aaa
קובץ:Tree aaa 1.svg|עץ יצירה 2 למילה aaa
</gallery>
מאידך, הדקדוק <math>S\to aS \ \epsilon</math> יוצר את אותה שפה (<math>aa^*</math>), ואינו דו משמעי.
[[קובץ:Tree aaa right.svg|80px|ממוסגר|ימין|עץ היצירה היחיד של המילה aaa בדקדוק שאינו דו-משמעי]]
 
{{תרגיל|שאלה=האם הדקדוק הבא דו משמעי? אם כן, מצא דקדוק חלופי שאינו דו משמעי.