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

בתורת השפות הפורמליות, אומרים כי דקדוק חסר הקשר מוצג ב**צורה הנורמלית של גרייבך** (אותה הגתה שילה גרייבך) אם כל כללי הגזירה שלו הם מהצורה A \rightarrow \sigma\alpha, כאשר \sigma סימן טרמינלי, A משתנה שאינו טרמינלי, ו-\alpha מילה המורכבת מאפס משתנים או יותר.

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

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

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

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

### בניית עזר 1
לכל כלל ב-P מהצורה A \rightarrow \sigma_1B\sigma_2, כאשר כל כללי B הם מהצורה B \rightarrow \gamma_1|\gamma_2|...|\gamma_n, נשמיט את הכלל A \rightarrow \sigma_1B\sigma_2 ונוסיף במקומו את הכללים B \rightarrow \sigma_1\gamma_1\sigma_2|\sigma_1\gamma_2\sigma_2|...|\sigma_1\gamma_n\sigma_2.

### בניית עזר 2
נפריד את הכללים של כל משתנה A לשתי קבוצות. בקבוצה הראשונה יהיו כל הכללים שגוזרים מילה שמתחילה בA, ובקבוצה השנייה כל שאר הכללים, כלומר הקבוצה הראשונה תכיל כללים מהצורה A \rightarrow A\sigma_1|A\sigma_2|...|A\sigma_mוהקבוצה השנייה תכיל את שאר הכללים שנגזרים מA, נניח A \rightarrow \gamma_1|\gamma_2|...|\gamma_n. נוסיף ל-V משתנה חדש, A' ונחליף את כל הכללים שA גוזר ב-P באופן הבא:

לכל 1\leq i \leq m נוסיף את הכללים:
* A' \rightarrow \alpha_i
* A' \rightarrow \alpha_iA'
ולכל 1\leq j \leq n נוסיף את הכללים:
* A \rightarrow \gamma_i
* A \rightarrow \gamma_iA'
כעת נציג את האלגוריתם תוך שימוש מתמיד בבניות העזר.

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

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

### שלב 2
נשים לב שאחרי שביצענו את שלב 1, כל כלל בקבוצת הכללים החדשה שלנו הוא מהצורה A_i \rightarrow \sigma\alpha כאשר \sigma טרמינל, או מהצורה A_i \rightarrow A_j\sigmaכאשר i \leq j, ובפרט כל הכללים שנגזרים מA_n הם מהצורה הראשונה. לכל כלל שנגזר מA_k החל מk=n-1 ועד k=1 נפעיל את בנייה 1 כדי לקבל כללים שכולם מהצורה A_k \rightarrow \sigma\alpha כאשר \sigma טרמינל.

### שלב 3
נדאג שגם כל הכללים של משתני העזר יהיו מהצורה A_k' \rightarrow \sigma\alpha כאשר \sigma טרמינל בעזרת בנייה 1.

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

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

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

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

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

## ראו גם
* דקדוק חסר הקשר
* הצורה הנורמלית של חומסקי

## לקריאה נוספת
* 

## הערות שוליים

קטגוריה:בלשנות
קטגוריה:אוטומטים
קטגוריה:שפות פורמליות