בתורת השפות הפורמליות, אומרים כי דקדוק חסר הקשר מוצג בצורה הנורמלית של גרייבך (אותה הגתה שילה גרייבך) אם כל כללי הגזירה שלו הם מהצורה ${\displaystyle A\rightarrow \sigma \alpha }$, כאשר ${\displaystyle \sigma }$ סימן טרמינלי, ${\displaystyle A}$ משתנה שאינו טרמינלי, ו-${\displaystyle \alpha }$ מילה המורכבת מאפס משתנים או יותר.^[1]

כל דקדוק המוגדר באמצעות הצורה הנורמלית של גרייבך הוא חסר הקשר, וכל דקדוק חסר הקשר ששפתו אינה מכילה את המילה הריקה יכול להיכתב באופן שקול כדקדוק בצורה הנורמלית של גרייבך.^[2]

גם לשפה שכן מכילה את המילה הריקה ניתן להגדיר דקדוק מהצורה הנורמלית של גרייבך, באמצעות הוספת הכלל ${\displaystyle S\rightarrow \varepsilon }$ לדקדוק שכל כלליו הם מהצורה שהוצגה מעלה.

יהי ${\displaystyle G=(V,T,P,S)}$ דקדוק חופשי הקשר שיוצר שפה כלשהי שלא מכילה את המילה הריקה (אם השפה מכילה את המילה הריקה, אז אחרי ביצוע האלגוריתם נוסיף את הכלל ${\displaystyle S\rightarrow \varepsilon }$ לקבלת דקדוק מהצורה המורחבת של גרייבך), ונניח ש- ${\displaystyle V=\{A_{1},...,A_{n}\}}$.

נגדיר שתי בניות עזר לפישוט האלגוריתם.

לכל כלל ב-${\displaystyle P}$ מהצורה ${\displaystyle A\rightarrow \sigma _{1}B\sigma _{2}}$, כאשר כל כללי ${\displaystyle B}$ הם מהצורה ${\displaystyle B\rightarrow \gamma _{1}|\gamma _{2}|...|\gamma _{n}}$, נשמיט את הכלל ${\displaystyle A\rightarrow \sigma _{1}B\sigma _{2}}$ ונוסיף במקומו את הכללים ${\displaystyle B\rightarrow \sigma _{1}\gamma _{1}\sigma _{2}|\sigma _{1}\gamma _{2}\sigma _{2}|...|\sigma _{1}\gamma _{n}\sigma _{2}}$.

נפריד את הכללים של כל משתנה ${\displaystyle A}$ לשתי קבוצות. בקבוצה הראשונה יהיו כל הכללים שגוזרים מילה שמתחילה ב${\displaystyle A}$, ובקבוצה השנייה כל שאר הכללים, כלומר הקבוצה הראשונה תכיל כללים מהצורה ${\displaystyle A\rightarrow A\sigma _{1}|A\sigma _{2}|...|A\sigma _{m}}$והקבוצה השנייה תכיל את שאר הכללים שנגזרים מ${\displaystyle A}$, נניח ${\displaystyle A\rightarrow \gamma _{1}|\gamma _{2}|...|\gamma _{n}}$. נוסיף ל-${\displaystyle V}$ משתנה חדש, ${\displaystyle A'}$ ונחליף את כל הכללים ש${\displaystyle A}$ גוזר ב-${\displaystyle P}$ באופן הבא:

לכל ${\displaystyle 1\leq i\leq m}$ נוסיף את הכללים:

• ${\displaystyle A'\rightarrow \alpha _{i}}$
• ${\displaystyle A'\rightarrow \alpha _{i}A'}$

ולכל ${\displaystyle 1\leq j\leq n}$ נוסיף את הכללים:

• ${\displaystyle A\rightarrow \gamma _{i}}$
• ${\displaystyle A\rightarrow \gamma _{i}A'}$

כעת נציג את האלגוריתם תוך שימוש מתמיד בבניות העזר.

בעבור ${\displaystyle A_{1}}$, אם קיימים כללים מהצורה ${\displaystyle A_{1}\rightarrow A_{1}\sigma }$, נשתמש בבניית עזר 2 כדי להוסיף לדקדוק משתנה ${\displaystyle A_{1}'}$ ונפעל על פי הבניה לתיקון כללי הגזירה.

לכל משתנה אחר, ${\displaystyle A_{i}}$ כאשר ${\displaystyle 1\leq i}$ ב-${\displaystyle V}$, תחילה נטפל בכללים מהצורה ${\displaystyle A_{i}\rightarrow A_{j}\sigma }$כאשר ${\displaystyle j\leq i}$ באמצעות הפעלת בניית עזר 1 על המשתנה ${\displaystyle A_{j}}$. לאחר מכן, נטפל בכללים מהצורה ${\displaystyle A_{k}\rightarrow A_{k}\sigma }$באמצעות בניית עזר 2, תוך הוספת המשתנה ${\displaystyle A_{k}'}$ והגדרת כללי בנייה 2.

נשים לב שאחרי שביצענו את שלב 1, כל כלל בקבוצת הכללים החדשה שלנו הוא מהצורה ${\displaystyle A_{i}\rightarrow \sigma \alpha }$ כאשר ${\displaystyle \sigma }$ טרמינל, או מהצורה ${\displaystyle A_{i}\rightarrow A_{j}\sigma }$כאשר ${\displaystyle i\leq j}$, ובפרט כל הכללים שנגזרים מ${\displaystyle A_{n}}$ הם מהצורה הראשונה. לכל כלל שנגזר מ${\displaystyle A_{k}}$ החל מ${\displaystyle k=n-1}$ ועד ${\displaystyle k=1}$ נפעיל את בנייה 1 כדי לקבל כללים שכולם מהצורה ${\displaystyle A_{k}\rightarrow \sigma \alpha }$ כאשר ${\displaystyle \sigma }$ טרמינל.

נדאג שגם כל הכללים של משתני העזר יהיו מהצורה ${\displaystyle A_{k}'\rightarrow \sigma \alpha }$ כאשר ${\displaystyle \sigma }$ טרמינל בעזרת בנייה 1.

כעת כל הכללים הם מהצורה ${\displaystyle A\rightarrow \sigma \alpha }$ או מהצורה ${\displaystyle A\rightarrow \sigma }$ כאשר ${\displaystyle \sigma }$ טרמינל ו-${\displaystyle \alpha }$ מורכב הן ממשתנים והן מסימנים טרמינלים.

מכיוון שהמטרה שלנו היא להגיע לדקדוק מהצורה של גרייבך, נצטרך לגרום ל${\displaystyle \alpha }$ להיות מורכבת אך ורק ממשתנים. אם כל ה${\displaystyle \alpha }$ בכל הכללים מורכבות ממשתנים בלבד, סיימנו. אחרת, קיימת ${\displaystyle \alpha }$ כך שמופיע בה משתנה טרמינלי ${\displaystyle \tau }$. לכל טרמינל כזה שנותר, נגדיר משתנה חדש ${\displaystyle B_{\tau }}$, נחליף את כל המופעים של ${\displaystyle \tau }$ בכל ${\displaystyle \alpha }$ שהוא מופיע בה ב${\displaystyle B_{\tau }}$, ונוסיף את הכלל ${\displaystyle B_{\tau }\rightarrow \tau }$.

כעת בידינו דקדוק מהצורה הנורמלית של גרייבך ששקול לדקדוק המקורי.

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

בנוסף, ניתן להשתמש בצורה הנורמלית של גרייבך למעבר מדקדוק חסר הקשר נתון לאוטומט מחסנית בעבור שפה מסוימת.

• דקדוק חסר הקשר
• הצורה הנורמלית של חומסקי

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000