אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/צורות נורמליות לדקדוקים חסרי הקשר

תבנית:אוטומטים ושפות פורמליות בפרק [[../../דקדוקים חסרי הקשר/]] ראינו כי ניתן להמיר כל אוטומט מחסנית לדקדוק ח"ה. יותר מכך, נשים לב לכללי הגזירה שנוצרים בתהליך. כל כלל גזירה נראה כמו אחת הצורות הבאות

$A\to BC$

$A\to xBy$

$A\to \epsilon$

כאשר $A,B,C$ משתנים ו-$x,y$ טרמינלים. כלומר, כל דקדוק חסר-הקשר ניתן להביע על-ידי דקדוק שכל כלל בו הוא אחד מהצורות לעיל. צורה זו אינה מינימלית. למשל, את הכלל $A\to xBy$ ניתן להחליף בכללים יותר פשוטים, בהן כל משתנה הופך או לשני משתנים או לאות בודדת. צורה זו ידועה בתור הצורה הנורמאלית של חומסקי.

הצורה הנורמאלית של גרייבאך

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