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

בהנתן דקדוק חסר-הקשר דו-משמעי, לא קיים אלגוריתם הממיר אותו לדקדוק לא דו-משמעי (אם קיים). יתר על כן, עצם השאלה האם דקדוק מסויים הוא דו-משמעי או לא, אינו בעיה כריעה - כלומר לא קיים אלגוריתם (מכונת טיורינג) המכריע את השפה

<center><math>L = \{ G \mid G \text{ is unambiguous grammar}\}</math></center>

 

{{אוטומטים ושפות פורמליות|מוגבל}}