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