הומומורפיזם (שפות פורמליות)

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

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

הרחבות

נוכל להרחיב את מושג ההומומורפיזם למילים ואף לשפות. יהיו שני א"ב ויהי הומומורפיזם .

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

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

נעיר שפעמים רבות, כשההקשר ברור משמיטים את סימני הכובעים.

דוגמה

ניתן דוגמה להומומורפיזם ולהרחבותיו. יהיו הא"ב . נגדיר הומומורפיזם באופן הבא:

.

לכן, מתקיים למשל כי

.

נעיין בשפה . אז

.

סגירות משפחות של שפות תחת הומומורפיזם

משפחת השפות הרגולריות סגורה תחת הומומורפיזם. כלומר, בהינתן רגולריות ו- הומומורפיזם, השפה גם רגולרית.

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

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

הומומורפיזם הפוך

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

לכל . אם כן, מעבירה כל מילה מעל לשפה מעל .

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

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

משפחת השפות הרגולריות סגורה תחת הומומורפיזם הפוך, וכן משפחת השפות החסרות-הקשר סגורה תחת הומומורפיזם הפוך.

סגירות משפחת השפות הרגולריות תחת הומומורפיזם הפוך

משפט: יהיו הומומורפיזם ו- שפה רגולרית. אז גם רגולרית.

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

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

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

טענת עזר: מתקיים לכל .

הוכחת טענת העזר: באינדוקציה על מבנה .

בסיס: אם נקבל כי

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

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

(הסבר למעברים: מעבר (2) הוא מהגדרת פונקציית המעברים המורחבת; מעבר (3) הוא מהנחת האינדוקציה על ; מעבר (4) הוא מהגדרת ; מעבר (5) הוא מהטענה ; מעבר (6) הוא מהגדרת ההומומורפיזם).

נמשיך בהוכחה. נראה ש-. אכן

כנדרש (הסבר למעברים: (1) הגדרת קבלה על ידי אוטומט סופי דטרמיניסטי; (2) טענת העזר; (3) כמו (1); (4) הגדרת הומומורפיזם הפוך).

סגירות משפחת השפות החסרות-הקשר תחת הומומורפיזם הפוך

משפט: יהיו הומומורפיזם ו- שפה חסרת-הקשר. אז גם חסרת-הקשר.

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

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

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

1. קריאת אות קלט על ידי :
לכל .

2. סימולציית - מסעי-:
לכל (אם מסמלצים מעבר "רגיל" של , ואם מסמלצים מסע- של ).

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

טענת עזר: לכל , אם אז .

כעת, כל שנותר להראות הוא ש-.

לקריאה נוספת

Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0