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

<center><math>S\to 0S1 \mid \epsilonvarepsilon \mid 01</math></center>

קל לראות כי ניתן ליצור את המילה 01 בשני אופנים שונים: <math>S\Rightarrow 0S1 \Rightarrow 0\epsilon1varepsilon1 = 01</math> אך גם <math>S\Rightarrow 01</math>. עבור דוגמא זו קל לשנות את הדקדוק כך שיהיה חד-משמעי. למשל <math>S\to 0S1 \mid \epsilonvarepsilon</math> יוצר את אותה השפה, ואינו דו-משמעי.

מאידך, הדקדוק <math>S\to aS \mid \epsilonvarepsilon</math> יוצר את אותה שפה (<math>aa^*</math>), ואינו דו משמעי.

<center><math>C\to 1C \mid \epsilonvarepsilon \qquad D\to 1D2 \mid \epsilonvarepsilon</math></center>