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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ אפסילונים
Gran (שיחה | תרומות)
שם
שורה 1:
{{אוטומטים ושפות פורמליות}}
נאמר שדקדוק הוא '''דו-משמעי''' (לעתים גם: רב-משמעי, 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> יוצר את אותה השפה, ואינו דו-משמעי.