הומומורפיזם (שפות פורמליות)
בתורת השפות הפורמליות, הומומורפיזם הוא פונקציה המעבירה אותיות מא"ב אחד למילים מעל א"ב אחר. באופן פורמלי, בהינתן $ \Sigma ,\Delta $ שני א"ב, הומומורפיזם הוא פונקציה $ h\colon \Sigma \to \Delta ^{*} $.
הרחבות
נוכל להרחיב את מושג ההומומורפיזם למילים ואף לשפות. יהיו $ \Sigma ,\Delta $ שני א"ב ויהי הומומורפיזם $ h\colon \Sigma \to \Delta ^{*} $.
- ההרחבה למילים של $ h $ היא פונקציה $ {\hat {h}}\colon \Sigma ^{*}\to \Delta ^{*} $ (כלומר, מעבירה מילים מעל $ \Sigma $ למילים מעל $ \Delta $) המוגדרת באופן הבא:
$ {\begin{aligned}{\hat {h}}(\varepsilon )&:=\varepsilon \\{\hat {h}}(w\sigma )&:={\hat {h}}(w)\cdot h(\sigma )\end{aligned}} $
נשים לב שנובע שאם $ w=\sigma _{1}\sigma _{2}\dots \sigma _{n}\in \Sigma ^{*} $ אז מההגדרה $ {\hat {h}}(w)=h(\sigma _{1})h(\sigma _{2})\dots h(\sigma _{n}) $, כלומר זהו שרשור המילים אליהן הועתקו אותיות המילה $ w $ על ידי $ h $ (וכן נובעת הטענה השימושית כי לכל $ w_{1},w_{2}\in \Sigma ^{*} $ מתקיים $ {\hat {h}}(w_{1}w_{2})={\hat {h}}(w_{1})\cdot {\hat {h}}(w_{2}) $). אם לכל $ \varepsilon \neq w\in \Sigma ^{*} $ (כאשר $ \varepsilon $ המילה הריקה) מתקיים $ h(w)\neq \varepsilon $ אז נאמר ש-$ {\hat {h}} $ היא $ {\boldsymbol {\varepsilon }} $-חופשית. - ההרחבה לשפות של $ h $ היא פונקציה $ {\hat {\hat {h}}}\colon 2^{\Sigma ^{*}}\to 2^{\Delta ^{*}} $ (כלומר, מעבירה שפות מעל $ \Sigma $ לשפות מעל $ \Delta $) המוגדרת:
$ {\hat {\hat {h}}}(L):=\left\{{\hat {h}}(w):w\in L\right\} $ לכל שפה $ L\subseteq \Sigma ^{*} $.
נעיר שפעמים רבות, כשההקשר ברור משמיטים את סימני הכובעים.
דוגמה
ניתן דוגמה להומומורפיזם ולהרחבותיו. יהיו הא"ב $ \Sigma =\{a,b\},\Delta =\{0,1,2\} $. נגדיר הומומורפיזם $ h\colon \Sigma \to \Delta ^{*} $ באופן הבא:
$ h(a)=012,h(b)=21 $.
לכן, מתקיים למשל כי
$ {\hat {h}}(bba)=h(b)h(b)h(a)=2121012 $.
נעיין בשפה $ L=\{a^{i}b^{j}:i,j\geq 0\} $. אז
$ {\hat {\hat {h}}}(L)=\left\{{\hat {h}}(a^{i}b^{j}):i,j\geq 0\right\}=\{(h(a))^{i}(h(b))^{j}:i,j\geq 0\}=\{(012)^{i}(21)^{j}:i,j\geq 0\} $.
סגירות משפחות של שפות תחת הומומורפיזם
משפחת השפות הרגולריות סגורה תחת הומומורפיזם. כלומר, בהינתן $ L\subseteq \Sigma ^{*} $ רגולריות ו-$ h\colon \Sigma \to \Delta ^{*} $ הומומורפיזם, השפה $ h(L)\subseteq \Delta ^{*} $ גם רגולרית.
למעשה ניתן להראות משפט חזק יותר, והוא סגירות שפות רגולריות תחת הצבה רגולרית.
באופן דומה, גם משפחת השפות החסרות-הקשר סגורה תחת הומומורפיזם, וניתן להראות שהיא אף סגורה תחת הצבה חסרת-הקשר.
הומומורפיזם הפוך
ניתן להגדיר הומומורפיזם הפוך. ההגדרה תהיה בהתאם להגדרת מקור תחת פונקציה. בהינתן הומומורפיזם $ h\colon \Sigma \to \Delta ^{*} $, ההומומורפיזם ההפוך שלו $ h^{-1}\colon \Delta ^{*}\to 2^{\Sigma ^{*}} $ יוגדר להיות:
$ h^{-1}(w):=\{x\in \Sigma ^{*}:h(x)=w\} $ לכל $ w\in \Delta ^{*} $. אם כן, $ h^{-1} $ מעבירה כל מילה מעל $ \Delta $ לשפה מעל $ \Sigma $.
ניתן לבצע הרחבה לשפות (כלומר $ h^{-1}\colon 2^{\Delta ^{*}}\to 2^{\Sigma ^{*}} $ ונשתמש באותו הסימון למען הנוחות) על ידי ההגדרה:
$ h^{-1}(L)=\{w\in \Sigma ^{*}:h(w)\in L\} $ לכל $ L\subseteq \Delta ^{*} $. כלומר כעת, $ h^{-1} $ מעבירה כל שפה מעל $ \Delta $ לשפה מעל $ \Sigma $. נעיר שבאופן שקול יכולנו גם להגדיר $ h^{-1}(L)=\bigcup _{w\in L}h^{-1}(w) $.
משפחת השפות הרגולריות סגורה תחת הומומורפיזם הפוך, וכן משפחת השפות החסרות-הקשר סגורה תחת הומומורפיזם הפוך.
סגירות משפחת השפות הרגולריות תחת הומומורפיזם הפוך
משפט: יהיו $ h\colon \Sigma \to \Delta ^{*} $ הומומורפיזם ו-$ L\subseteq \Delta ^{*} $ שפה רגולרית. אז גם $ h^{-1}(L) $ רגולרית.
הוכחה: מכיוון ש-$ L $ רגולרית, לפי ההגדרה קיים אוטומט סופי דטרמיניסטי $ A=(\Delta ,Q,q_{0},F,\delta ) $ שמקבל אותה (משמע $ L(A)=L $). נבנה אוטומט סופי $ A' $ שמקבל את $ h^{-1}(L) $, ומכאן שהיא רגולרית.
רעיון הבניה הוא כדלהלן: בהינתן $ w\in \Sigma ^{*} $, על מנת לקבוע את שייכותה ל-$ h^{-1}(L) $, נרצה להפעיל סימולציה של $ A $ על $ h(w) $ כדי לקבוע את שייכותה ל-$ L $ (וזה יהיה אופן פעילות $ A' $). אז אם $ w=\sigma _{1}\sigma _{2}\dots \sigma _{n} $, נרצה לבדוק האם $ h(w)=h(\sigma _{1})h(\sigma _{2})\dots h(\sigma _{n})\in L $. נרצה אם כן, שכאשר האוטומט $ A' $ נמצא במצב $ q\in Q $ ומקבל אות קלט $ \sigma \in \Sigma $, הוא "יפעיל" סימולציה של $ A $ מהמצב $ q $ עם מילת הקלט $ h(\sigma ) $.
מהמוטיבציה לעיל, נגדיר את האוטומט הסופי דטרמיניסטי $ A'=(\Sigma ,Q,q_{0},F,\delta ') $ עם פונקציית המעברים $ \delta '(q,\sigma ):={\hat {\delta }}(q,h(\sigma )) $ לכל $ q\in Q $ ו-$ \sigma \in \Sigma $. כרגיל במשפטים כאלו, יהיה נוח להוכיח טענת עזר:
טענת עזר: מתקיים $ {\hat {\delta '}}(q_{0},w)={\hat {\delta }}(q_{0},h(w)) $ לכל $ w\in \Sigma ^{*} $.
הוכחת טענת העזר: באינדוקציה על מבנה $ w $.
בסיס: אם $ w=\varepsilon $ נקבל כי
$ {\hat {\delta '}}(q_{0},\varepsilon )=q_{0}={\hat {\delta }}(q_{0},\varepsilon )=\delta (q_{0},h(\varepsilon )) $
מהגדרת פונקציית המעברים המורחבת וכן מהגדרת ההומומורפיזם. למילים באורך $ 1 $ הטענה מתקיימת ישירות מהגדרתנו ל-$ \delta ' $.
צעד: נניח נכונות למילים באורך $ n $ ונראה נכונות למילים באורך $ n+1 $. תהי $ w=u\sigma \in \Sigma ^{*} $ כאשר $ |w|=n $. אז
$ {\hat {\delta '}}(q_{0},w)={\hat {\delta '}}(q_{0},u\sigma )=\delta '({\hat {\delta '}}(q_{0},u),\sigma )=\delta '({\hat {\delta }}(q_{0},h(u)),\sigma )={\hat {\delta }}({\hat {\delta }}(q_{0},h(u)),h(\sigma ))={\hat {\delta }}(q_{0},h(u)h(\sigma ))={\hat {\delta }}(q_{0},h(u\sigma ))={\hat {\delta }}(q_{0},h(w)) $
(הסבר למעברים: מעבר (2) הוא מהגדרת פונקציית המעברים המורחבת; מעבר (3) הוא מהנחת האינדוקציה על $ u $; מעבר (4) הוא מהגדרת $ \delta ' $; מעבר (5) הוא מהטענה $ {\hat {\delta }}({\hat {\delta }}(q,w_{1}),w_{2})={\hat {\delta }}(q,w_{1}w_{2}) $; מעבר (6) הוא מהגדרת ההומומורפיזם). $ \blacksquare $
נמשיך בהוכחה. נראה ש-$ L(A')=h^{-1}(L) $. אכן
$ w\in L(A')\Leftrightarrow {\hat {\delta '}}(q_{0},w)\in F\Leftrightarrow {\hat {\delta }}(q_{0},h(w))\in F\Leftrightarrow h(w)\in L\Leftrightarrow w\in h^{-1}(L) $
כנדרש (הסבר למעברים: (1) הגדרת קבלה על ידי אוטומט סופי דטרמיניסטי; (2) טענת העזר; (3) כמו (1); (4) הגדרת הומומורפיזם הפוך). $ \blacksquare $
סגירות משפחת השפות החסרות-הקשר תחת הומומורפיזם הפוך
משפט: יהיו $ h\colon \Sigma \to \Delta ^{*} $ הומומורפיזם ו-$ L\subseteq \Delta ^{*} $ שפה חסרת-הקשר. אז גם $ h^{-1}(L) $ חסרת-הקשר.
רעיון ההוכחה: לא ניתן את ההוכחה המלאה, אך ניתן את הרעיון הכללי ובנייה. תהי $ L\subseteq \Delta ^{*} $ שפה חסרת הקשר. אז קיים אוטומט מחסנית $ M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\dashv ,F) $ שמקבל אותה באמצעות מצבים מקבלים (כלומר $ L_{f}(M)=L $). נבנה אוטומט מחסנית $ M' $ שמקבל את $ h^{-1}(L) $, ולכן היא חסרת-הקשר. חשוב לשים לב שהאוטומט לא יכול לרוקן יותר מאות אחת מראש המחסנית בצעד אחד. לכן, בהינתן אות קלט $ \sigma \in \Sigma $, $ M' $ לא תמיד יוכל לסמלץ את $ M $ עבור מילת הקלט $ h(\sigma ) $ בצעד אחד. ואמנם, השימוש במסעי-$ \varepsilon $ יבוא לעזרנו. כלומר, האוטומט $ M' $ יקרא אות קלט $ \sigma \in \Sigma $, יסמלץ את $ M $ עם מילת הקלט $ h(\sigma ) $ בעזרת מסעי-$ \varepsilon $, ואז יקרא עוד אות קלט ויפעל באופן זהה, עד אשר יסיים את קריאת המילה, ואז יגיע למצב מקבל.
נגדיר את מצבי $ M' $ להיות $ Q':=Q\times \Delta ' $ כאשר $ \Delta ' $ הוא אוסף כל המילים מעל $ \Delta $ באורך לכל היותר $ \max\{|h(\sigma )|:\sigma \in \Sigma \} $, כלומר האורך המקסימלי שייתכן לתת מילת קלט כלשהו ש-$ M' $ יצטרך לסמלץ. כלומר, זוג $ (q,w)\in Q' $ מייצג מצב $ q $ בו $ M $ נמצא, ויתרת מילה $ w $ שעליו לקרוא. המצב ההתחלתי יהיה $ q_{0}':=(q_{0},\varepsilon ) $ (כי תחילה אין מילת קלט שעל $ M $ לקרוא). המצבים המקבלים יהיו $ F':=F\times \{\varepsilon \} $ כי על $ M $ להגיע למצב מקבל, ואין עוד יתרת מילה שעליו לקרוא. אם כן, $ M'=(Q',\Sigma ,\Gamma ,\delta ',(q_{0},\varepsilon ),\dashv ,F\times \{\varepsilon \}) $.
נותרה הגדרת פונקציית המעברים. נגדיר אותה בהתאם למוטיבציה שלעיל:
1. קריאת אות קלט על ידי $ M' $:
$ \delta '((q,\varepsilon ),\sigma ,Z):=\{((q,h(\sigma )),Z)\} $ לכל $ q\in Q,\sigma \in \Sigma ,Z\in \Gamma $.
2. סימולציית $ M $ - מסעי-$ \varepsilon $:
$ \delta '((q,\tau w),\varepsilon ,Z):=\{((p,w),\alpha ):(p,\alpha )\in \delta (q,\tau ,Z)\} $ לכל $ q\in Q,Z\in \Gamma ,\tau \in \Delta \cup \{\varepsilon \},w\in \Sigma ^{*} $ (אם $ \tau \in \Delta $ מסמלצים מעבר "רגיל" של $ M $, ואם $ \tau =\varepsilon $ מסמלצים מסע-$ \varepsilon $ של $ M $).
זו בדיוק הבנייה שעונה לתיאור שנתנו. להמשך ההוכחה הפורמלית, כדאי להוכיח את טענת העזר הבאה, שמשקפת את אופן פעולת $ M' $ כפי שתיארנו:
טענת עזר: לכל $ q,p\in Q,\,w\in \Sigma ^{*},\,\alpha ,\beta \in \Gamma ^{*} $, אם $ (q,h(w),\alpha )\vdash _{M}^{*}(p,\varepsilon ,\beta ) $ אז $ ((q,\varepsilon ),w,\alpha )\vdash _{M'}^{*}((p,\varepsilon ),\varepsilon ,\beta ) $.
כעת, כל שנותר להראות הוא ש-$ L_{f}(M')=h^{-1}(L) $.
לקריאה נוספת
- שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 2001
- שפות רגולריות - תכונות סגור (חלק ב') בבלוג "לא מדויק"
שגיאות פרמטריות בתבנית:מיון ויקיפדיה
שימוש בפרמטרים מיושנים [ דרגה ] הומומורפיזם (שפות פורמליות)29800059