אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/דו-משמעות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
תרגיל |
מ תיקונימים |
||
שורה 1:
נאמר שדקדוק הוא '''דו-משמעי''' אם קיימת
<center><math>S\to 0S1 \mid \epsilon \mid 01</math></center>
קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: <math>S\Rightarrow 0S1 \Rightarrow 0\epsilon1 = 01</math> אך גם <math>S\to 01</math>. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל <math>S\
{{תרגיל|שאלה=האם הדקדוק הבא דו משמעי? אם כן, מצא דקדוק חלופי שאינו דו משמעי.
שורה 21:
== כריעות בעיית הדו-משמעות==
בהנתן דקדוק חסר-הקשר דו-משמעי, לא קיים אלגוריתם הממיר אותו לדקדוק לא דו-משמעי (אם
<center><math>L = \{ G \mid G \text{ is unambiguous grammar}\}</math></center>
(זהו נושא מתקדם השייך לקורס [[מבוא לחישוביות]])
| |||