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

ממוזער|עץ תחביר מופשט  של הביטוי האריתמטי <math>a^2+4b</math>. התחביר לדוגמה ('''למעלה''') וצורת חומסקי המתאימה לו ('''למטה''')

בתורת השפות הפורמליות, אומרים כי דקדוק חסר הקשר ניתן להצגה ב**צורה הנורמלית של חומסקי** (אותה הגה נועם חומסקי) אם כל כללי הגזירה שלו הם מהצורה הבאה:

:A \to BC
:A \to \alpha
:S \to \varepsilon

כאשר A,B ו-C הם משתנים שאינם טרמינלים, \alpha היא טרמינל, S היא משתנה הגזירה ההתחלתי ו-\varepsilon היא המחרוזת הריקה. כמו כן B ו-C לא יכולים להיות המשתנה ההתחלתי, וכלל הגזירה השלישי מופיע בדקדוק אם"ם \varepsilon \isin L(G), כאשר L(G) היא השפה הנגזרת מ-G.

כל דקדוק המוגדר באמצעות הצורה הנורמלית של חומסקי הוא חסר הקשר, וכל דקדוק חסר הקשר יכול להיכתב באופן שקול כדקדוק בצורה הנורמלית של חומסקי (כלומר, ששפותיהם זהות). כיום קיימים מספר אלגוריתמים שעושים את ההעברות הנ"ל בין דקדוקים. החיסרון של שינויים אלו הוא שהם יכולים לגרום להתנפחות לא רצויה בגודל הדקדוק (המוגדר על ידי סכום הגדלים של כללי הגזירה שלו). אלגוריתמים שונים יכולים לקחת דקדוק בגודל |G| ולהופכו לדקדוק בגדלים הנעים, במקרה הגרוע ביותר, בין |G|^2 לבין 2^{2|G|}.

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

דקדוק פורמלי יופיע ב**צורה המצומצמת של חומסקי** אם כל כללי הגזירה שלו הם מהצורה:
:A \to BC
:A \to \alpha

כאשר A, B ו-C הם משתנים שאינם טרמינלים. כאשר משתמשים בהגדרה זו, B או C רשאים להיות המשתנה ההתחלתי. רק דקדוקים חסרי הקשר שלא מכילים את המחרוזת הריקה יכולים להיכתב בצורה המצומצמת של חומסקי.

### הצורה הנורמלית של פלויד
במאמר שפרסם דונלד קנות' בנושא BNF , הוא רמז לתחביר BNF שבו כל ההגדרות יכולות להיכתב ב*צורה הנורמלית של פלויד*, שהיא:

: \langle A \rangle ::= \, \langle B \rangle \mid \langle C \rangle
: \langle A \rangle ::= \, \langle B \rangle \langle C \rangle
: \langle A \rangle ::=\, a

כאשר \langle A \rangle , \langle B \rangle  ו-\langle C \rangle  הם משתנים שאינם טרמינלים, ו-a הוא טרמינל, וזאת כיוון שרוברט פלויד הוכיח כי כל תחביר BNF יכול להפוך לצורה הזו ב-1961. פלויד הוא זה שטבע את המושג, היות ש"מאז ללא ספק הרבה אנשים השתמשו באופן עצמאי בעובדה פשוטה זו בעבודתם, והנקודה היא רק נלווית לשיקולים העיקריים בעבודתו של פלויד".

## הפיכת תחביר לצורה הנורמלית של חומסקי
# הגדרת S_0

#: הגדרת משתנה התחלתי חדש, S_0, וכלל גזירה חדש, S_0 \rightarrow S, כאשר S הוא המשתנה ההתחלתי הקודם.
# הסרת כל *כללי ה-<math>\varepsilon</math>*
#: כללי ה-\varepsilon הם כללים מהצורה A \rightarrow \varepsilon, כאשר A \not= S_0 וכן A \in V, כאשר V זו קבוצת המשתנים של הדקדוק חסר ההקשר.
#: הסרת כל הכללים עם \varepsilon בצד הימני שלהם. עבור כל כלל מהצורה A \rightarrow \varepsilon שהסרנו, נעבור על כל הכללים שמכילים את A בצד הימני. עבור כל כלל כזה, נוסיף אוסף של כללים שיהווה את כל הקומבינציות שבהן A  מוחלפת על ידי \varepsilon. אם כלל מכיל את היחידון {A} בצד ימין, נוסיף אוסף מתאים של כללים עבור המשתנה הנ"ל, ולא נוסיף את הכלל ממנו ל-\varepsilon אם טיפלנו כבר במקרה זה.
#: לדוגמה, נוכל לראות את הדקדוק הבא:
#:: S \rightarrow AbA \mid B
#:: B \rightarrow b \mid c
#:: A \rightarrow \varepsilon
#: ל-G יש כלל \varepsilon אחד. כשנסיר אותו, נקבל את הכללים הבאים:
#:: S \rightarrow AbA \mid Ab \mid bA \mid b \mid B
#:: B \rightarrow b \mid c
#: על מנת לטפל באמת בכל האפשרויות שבהן יכול היה להתקיים A \rightarrow \varepsilon, הוספנו 3 כללים חדשים.
# הסרת כל *כללי היחידה*
#: כללי יחידה הם כללים מהצורה A \rightarrow B. אחרי שכל כללי ה-\varepsilon הוסרו, ניתן להסיר כללים אלה. ההסרה מתבצעת באופן הבא:
#: על מנת להסיר את הכלל A \rightarrow B, נעבור את כל הכללים מהצורה  B \rightarrow U, ונוסיף את הכללים A \rightarrow U אלא אם כן זהו כלל יחידה שהסרנו כבר.
# הפיכת כל שאר כללי הגזירה לצורה הנורמלית של חומסקי
#: בשלב זה נחליף את כל הכללים מהצורה: A \rightarrow u_1 u_2 \dotso u_k, k \ge 3, u_1 \in V \cup \Sigma, לכללים: A \rightarrow u_1 A_1, A_1 \rightarrow u_2 A_2, \dotsc, A_{k-2} \rightarrow u_{k-1} u_k כאשר כל המשתנים מהצורה A_i הם משתנים חדשים.
#: לסיכום, אם u_i \in \Sigma, נחליף את u_i במשתנה חדש V_i, וניצור את כלל הגזירה V_i \rightarrow u_i.

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

כמו כן, לצורה הנורמלית של חומסקי יתרון בניתוח הכרעה של שפות. כאשר דקדוק מורכב בצורה הנורמלית של חומסקי, מילה בגודל |w| יכולה להיווצר על ידי לכל היותר 2 |w|-1 כללי גזירה (פרט למילה הריקה, שנגזרת מיד), ובצורה זו ניתן לבדוק האם שפה חסרת הקשר אינה שווה ל\Sigma ^* באמצעות מכונת טיורינג, על ידי הרצה של כל המילים בסדר Minlex למשך 2 |w|-1 כללי גזירה, וכך אם יש מילה שלא שייכת לשפה נמצא אותה תוך זמן סופי ונדחה.

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

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

* John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. *Introduction to Automata Theory, Languages, and Computation*, 3rd Edition, Addison-Wesley, 2006.  *(see subsection 7.1.5, page 272.)
*Lange, Martin and Leiß, Hans. [http://ddi.cs.uni-potsdam.de/InformaticaDidactica/LangeLeiss2009.pdf *To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm.''] Informatica Didactica 8, 2009.


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

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