אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/צורות נורמליות לדקדוקים חסרי הקשר: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←הצורה הנורמאלית של גרייבאך: הרחבה |
|||
שורה 57:
<center><math>A\to x \gamma</math></center>
כאשר <math>x\in\Sigma</math> הוא טרמינל, ו <math>\gamma \in V^*</math> מחרוזת של (אפס או יותר) משתנים.}}
הוכחת המשפט חורגת מגבולות קורס זה. הרעיון הכללי הוא לפתח כל כלל גזירה עד שיופיע טרמינל במיקום הראשון. הקושי בהוכחה הינו קיומם האפשרי של מעגלים היוצרים עוד ועוד משתנים במיקום הראשון. בעיה זו מצריכה "מעקף" - הוספת משתנה היוצר טרמינל במקום הראשון, ולאחריו את סדרת המשתנים שאולי היו נוצרים בסדרת הגזירות היוצרת את אותו טרמינל.
{{אוטומטים ושפות פורמליות|מוגבל}}
[[קטגוריה:אוטומטים ושפות פורמליות]]
| |||