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

בתורת השפות הפורמליות, **הומומורפיזם** הוא פונקציה המעבירה אותיות מא"ב אחד למילים מעל א"ב אחר. באופן פורמלי, בהינתן \Sigma,\Delta שני א"ב, הומומורפיזם הוא פונקציה h \colon \Sigma \to \Delta^*.

## הרחבות
נוכל להרחיב את מושג ההומומורפיזם למילים ואף לשפות. יהיו \Sigma,\Delta שני א"ב ויהי הומומורפיזם h \colon \Sigma \to \Delta^*.
* **ההרחבה למילים** של h היא פונקציה \hat{h} \colon \Sigma^* \to \Delta^* (כלומר, מעבירה מילים מעל \Sigma למילים מעל \Delta) המוגדרת באופן הבא:  \begin{align}
\hat{h}(\varepsilon) &:= \varepsilon \\
\hat{h}(w\sigma) &:= \hat{h}(w) \cdot h(\sigma)
\end{align}  נשים לב שנובע שאם 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
* שפות רגולריות - תכונות סגור (חלק ב') בבלוג "לא מדויק"

קטגוריה:שפות פורמליות
קטגוריה:אוטומטים