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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שימושים

מעבר לחשיבות התאורטית שלו, נעשה שימוש בהמרה לצורה הנורמלית של חומסקי בכמה אלגוריתמים כעיבוד מקדים, לדוגמה אלגוריתם CYK (אנ')[6].

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

ראו גם

לקריאה נוספת

הערות שוליים

  1. ^ Hopcroft, Ullman (1979); sect.4, p.106
  2. ^ Noam Chomsky (1959). "On Certain Formal Properties of Grammars" (PDF). Information and Control. 2: 137–167.
  3. ^ טרמינל הוא הסימן הבסיסי בשפה שמוגדרת על ידי דקדוק. בעצם, טרמינלים הם האותיות בשפה, בעוד שמשתנים שאינם טרמינלים הם אלו ש"נגזרים" באמצעות כללי הגזירה לטרמינלים ולמשתנים נוספים שאינם טרמינלים
  4. ^ Hopcroft and Ullman 1978
  5. ^ 5.0 5.1 Donald E. Knuth. 1964. Backus Normal Form vs. Backus Naur Form. Communications of the ACM, 7(12):735–736, December.
  6. ^ אלגוריתם על שם Cocke-Younger-Kasami שמפרק (Parse) משפט המורכב מדקדוק חסר הקשר למרכיביו
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0