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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

בתורת השפות הפורמליות, אומרים כי דקדוק חסר הקשר מוצג בצורה הנורמלית של גרייבך (אותה הגתה שילה גרייבך) אם כל כללי הגזירה שלו הם מהצורה Aσα, כאשר σ סימן טרמינלי, A משתנה שאינו טרמינלי, ו-α מילה המורכבת מאפס משתנים או יותר.[1]

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

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

אלגוריתם להפיכת תחביר לצורה הנורמלית של גרייבך[1]

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

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

בניית עזר 1

לכל כלל ב-P מהצורה Aσ1Bσ2, כאשר כל כללי B הם מהצורה Bγ1|γ2|...|γn, נשמיט את הכלל Aσ1Bσ2 ונוסיף במקומו את הכללים Bσ1γ1σ2|σ1γ2σ2|...|σ1γnσ2.

בניית עזר 2

נפריד את הכללים של כל משתנה A לשתי קבוצות. בקבוצה הראשונה יהיו כל הכללים שגוזרים מילה שמתחילה בA, ובקבוצה השנייה כל שאר הכללים, כלומר הקבוצה הראשונה תכיל כללים מהצורה AAσ1|Aσ2|...|Aσmוהקבוצה השנייה תכיל את שאר הכללים שנגזרים מA, נניח Aγ1|γ2|...|γn. נוסיף ל-V משתנה חדש, A ונחליף את כל הכללים שA גוזר ב-P באופן הבא:

לכל 1im נוסיף את הכללים:

  • Aαi
  • AαiA

ולכל 1jn נוסיף את הכללים:

  • Aγi
  • AγiA

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

שלב 1

בעבור A1, אם קיימים כללים מהצורה A1A1σ, נשתמש בבניית עזר 2 כדי להוסיף לדקדוק משתנה A1 ונפעל על פי הבניה לתיקון כללי הגזירה.

לכל משתנה אחר, Ai כאשר 1i ב-V, תחילה נטפל בכללים מהצורה AiAjσכאשר ji באמצעות הפעלת בניית עזר 1 על המשתנה Aj. לאחר מכן, נטפל בכללים מהצורה AkAkσבאמצעות בניית עזר 2, תוך הוספת המשתנה Ak והגדרת כללי בנייה 2.

שלב 2

נשים לב שאחרי שביצענו את שלב 1, כל כלל בקבוצת הכללים החדשה שלנו הוא מהצורה Aiσα כאשר σ טרמינל, או מהצורה AiAjσכאשר ij, ובפרט כל הכללים שנגזרים מAn הם מהצורה הראשונה. לכל כלל שנגזר מAk החל מk=n1 ועד k=1 נפעיל את בנייה 1 כדי לקבל כללים שכולם מהצורה Akσα כאשר σ טרמינל.

שלב 3

נדאג שגם כל הכללים של משתני העזר יהיו מהצורה Akσα כאשר σ טרמינל בעזרת בנייה 1.

שלב 4

כעת כל הכללים הם מהצורה Aσα או מהצורה Aσ כאשר σ טרמינל ו-α מורכב הן ממשתנים והן מסימנים טרמינלים.

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

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

שימושים

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

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

ראו גם

לקריאה נוספת

הערות שוליים

  1. ^ 1 2 שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000, עמ' 103-109
  2. ^ שילה גרייבך, "A New Normal-Form Theorem for Context-Free Phrase Structure Grammars", הז'ורנל של ACM, ינואר 1965