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

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

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

כאשר , ו- הם משתנים שאינם טרמינלים, היא טרמינל [3], היא משתנה הגזירה ההתחלתי ו- היא המחרוזת הריקה. כמו כן ו- לא יכולים להיות המשתנה ההתחלתי, וכלל הגזירה השלישי מופיע בדקדוק אם"ם , כאשר היא השפה הנגזרת מ-.

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

הגדרות שקולות

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

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

דקדוק פורמלי יופיע בצורה המצומצמת של חומסקי אם כל כללי הגזירה שלו הם מהצורה:

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

הצורה הנורמלית של פלויד

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

כאשר , ו- הם משתנים שאינם טרמינלים, ו- הוא טרמינל, וזאת כיוון ש רוברט פלויד ( אנ') הוכיח כי כל תחביר BNF יכול להפוך לצורה הזו ב-1961 [5]. פלויד הוא זה שטבע את המושג, היות ש"מאז ללא ספק הרבה אנשים השתמשו באופן עצמאי בעובדה פשוטה זו בעבודתם, והנקודה היא רק נלווית לשיקולים העיקריים בעבודתו של פלויד" [5].

Other Languages