הצגת המקור של הדף "הומומורפיזם (שפות פורמליות)"

בתורת [[שפה פורמלית|השפות הפורמליות]], '''הומומורפיזם''' הוא פונקציה המעבירה אותיות מא"ב אחד למילים מעל א"ב אחר. באופן פורמלי, בהינתן <math>\Sigma,\Delta</math> שני א"ב, הומומורפיזם הוא פונקציה <math>h \colon \Sigma \to \Delta^*</math>.

== הרחבות ==
נוכל להרחיב את מושג ההומומורפיזם למילים ואף לשפות. יהיו <math>\Sigma,\Delta</math> שני א"ב ויהי הומומורפיזם <math>h \colon \Sigma \to \Delta^*</math>.
* '''ההרחבה למילים''' של <math>h</math> היא פונקציה <math>\hat{h} \colon \Sigma^* \to \Delta^*</math> (כלומר, מעבירה מילים מעל <math>\Sigma</math> למילים מעל <math>\Delta</math>) המוגדרת באופן הבא: {{ש}} <math>\begin{align}
\hat{h}(\varepsilon) &:= \varepsilon \\
\hat{h}(w\sigma) &:= \hat{h}(w) \cdot h(\sigma)
\end{align}</math> {{ש}} נשים לב שנובע שאם <math>w = \sigma_1 \sigma_2 \dots \sigma_n \in \Sigma^*</math> אז מההגדרה <math>\hat{h}(w) = h(\sigma_1) h(\sigma_2) \dots h(\sigma_n)</math>, כלומר זהו שרשור המילים אליהן הועתקו אותיות המילה <math>w</math> על ידי <math>h</math> (וכן נובעת הטענה השימושית כי לכל <math>w_1,w_2 \in \Sigma^*</math> מתקיים <math>\hat{h}(w_1 w_2) = \hat{h}(w_1) \cdot \hat{h}(w_2)</math>). אם לכל <math>\varepsilon \neq w \in \Sigma^*</math> (כאשר <math>\varepsilon</math> [[מחרוזת ריקה (תכנות)|המילה הריקה]]) מתקיים <math>h(w) \neq \varepsilon</math> אז נאמר ש-<math>\hat{h}</math> היא <math>\boldsymbol{\varepsilon}</math>'''-חופשית'''.
*'''ההרחבה לשפות''' של <math>h</math> היא פונקציה <math>\hat{\hat{h}} \colon 2^{\Sigma^*} \to 2^{\Delta^*}</math> (כלומר, מעבירה שפות מעל <math>\Sigma</math> לשפות מעל <math>\Delta</math>) המוגדרת: {{ש}} <math>\hat{\hat{h}}(L) := \left\{ \hat{h}(w) : w \in L \right\}</math> לכל שפה <math>L \subseteq \Sigma^*</math>.

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

== דוגמה ==
ניתן דוגמה להומומורפיזם ולהרחבותיו. יהיו הא"ב <math>\Sigma = \{a,b\}, \Delta = \{0,1,2\}</math>. נגדיר הומומורפיזם <math>h \colon \Sigma \to \Delta^*</math> באופן הבא:

<math>h(a) = 012, h(b) = 21</math>.

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

<math>\hat{h}(bba) = h(b) h(b) h(a) = 2121012</math>.

נעיין בשפה <math>L = \{a^i b^j : i,j \geq 0\}</math>. אז

<math>\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\}</math>.

== סגירות משפחות של שפות תחת הומומורפיזם ==
משפחת [[שפה רגולרית|השפות הרגולריות]] סגורה תחת הומומורפיזם. כלומר, בהינתן <math>L \subseteq \Sigma^*</math> רגולריות ו-<math>h \colon \Sigma \to \Delta^*</math> הומומורפיזם, השפה <math>h(L) \subseteq \Delta^*</math> גם רגולרית.

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

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

== הומומורפיזם הפוך ==
ניתן להגדיר הומומורפיזם הפוך. ההגדרה תהיה בהתאם להגדרת מקור תחת פונקציה. בהינתן הומומורפיזם <math>h \colon \Sigma \to \Delta^*</math>, '''ההומומורפיזם ההפוך''' שלו <math>h^{-1} \colon \Delta^* \to 2^{\Sigma^*}</math> יוגדר להיות:

<math>h^{-1}(w) := \{x \in \Sigma^* : h(x) = w\}</math> לכל <math>w \in \Delta^*</math>. אם כן, <math>h^{-1}</math> מעבירה כל '''מילה''' מעל <math>\Delta</math> ל'''שפה''' מעל <math>\Sigma</math>.

ניתן לבצע '''הרחבה לשפות''' (כלומר <math>h^{-1} \colon 2^{\Delta^*} \to 2^{\Sigma^*}</math> ונשתמש באותו הסימון למען הנוחות) על ידי ההגדרה:

<math>h^{-1}(L) = \{w \in \Sigma^* : h(w) \in L\}</math> לכל <math>L \subseteq \Delta^*</math>. כלומר כעת, <math>h^{-1}</math> מעבירה כל '''שפה''' מעל <math>\Delta</math> ל'''שפה''' מעל <math>\Sigma</math>. נעיר שבאופן שקול יכולנו גם להגדיר <math>h^{-1}(L) = \bigcup_{w \in L} h^{-1}(w)</math>.

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

=== סגירות משפחת השפות הרגולריות תחת הומומורפיזם הפוך ===
'''''משפט:''''' יהיו <math>h \colon \Sigma \to \Delta^*</math> הומומורפיזם ו-<math>L \subseteq \Delta^*</math> שפה רגולרית. אז גם <math>h^{-1}(L)</math> רגולרית.

'''''הוכחה:''''' מכיוון ש-<math>L</math> רגולרית, לפי ההגדרה קיים [[אוטומט סופי דטרמיניסטי]] <math>A = (\Delta,Q,q_0,F,\delta)</math> שמקבל אותה (משמע <math>L(A) = L</math>). נבנה אוטומט סופי <math>A'</math> שמקבל את <math>h^{-1}(L)</math>, ומכאן שהיא רגולרית.

'''רעיון הבניה''' הוא כדלהלן: בהינתן <math>w \in \Sigma^*</math>, על מנת לקבוע את שייכותה ל-<math>h^{-1}(L)</math>, נרצה להפעיל סימולציה של <math>A</math> על <math>h(w)</math> כדי לקבוע את שייכותה ל-<math>L</math> (וזה יהיה אופן פעילות <math>A'</math>). אז אם <math>w = \sigma_1 \sigma_2 \dots \sigma_n</math>, נרצה לבדוק האם <math>h(w) = h(\sigma_1) h(\sigma_2) \dots h(\sigma_n) \in L</math>. נרצה אם כן, שכאשר האוטומט <math>A'</math> נמצא במצב <math>q \in Q</math> ומקבל אות קלט <math>\sigma \in \Sigma</math>, הוא "יפעיל" סימולציה של <math>A</math> מהמצב <math>q</math> עם מילת הקלט <math>h(\sigma)</math>.

מהמוטיבציה לעיל, נגדיר את האוטומט הסופי דטרמיניסטי <math>A' = (\Sigma,Q,q_0,F,\delta')</math> עם פונקציית המעברים <math>\delta'(q,\sigma) := \hat{\delta}(q,h(\sigma))</math> לכל <math>q \in Q</math> ו-<math>\sigma \in \Sigma</math>. כרגיל במשפטים כאלו, יהיה נוח להוכיח טענת עזר:

'''טענת עזר:''' מתקיים <math>\hat{\delta'}(q_0,w) = \hat{\delta}(q_0,h(w))</math> לכל <math>w \in \Sigma^*</math>.

'''הוכחת טענת העזר:''' באינדוקציה על מבנה <math>w</math>.

בסיס: אם <math>w = \varepsilon</math> נקבל כי

<math>\hat{\delta'}(q_0,\varepsilon) = q_0 = \hat{\delta}(q_0,\varepsilon) = \delta(q_0,h(\varepsilon))</math>

מהגדרת פונקציית המעברים המורחבת וכן מהגדרת ההומומורפיזם. למילים באורך <math>1</math> הטענה מתקיימת ישירות מהגדרתנו ל-<math>\delta'</math>.

צעד: נניח נכונות למילים באורך <math>n</math> ונראה נכונות למילים באורך <math>n+1</math>. תהי <math>w = u\sigma \in \Sigma^*</math> כאשר <math>|w| = n</math>. אז

<math>\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))</math>

(הסבר למעברים: מעבר (2) הוא מהגדרת פונקציית המעברים המורחבת; מעבר (3) הוא מהנחת האינדוקציה על <math>u</math>; מעבר (4) הוא מהגדרת <math>\delta'</math>; מעבר (5) הוא מהטענה <math>\hat{\delta}(\hat{\delta}(q,w_1),w_2) = \hat{\delta}(q,w_1 w_2)</math>; מעבר (6) הוא מהגדרת ההומומורפיזם). <math>\blacksquare</math>

נמשיך בהוכחה. נראה ש-<math>L(A') = h^{-1}(L)</math>. אכן

<math>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)</math>

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

=== סגירות משפחת השפות החסרות-הקשר תחת הומומורפיזם הפוך ===
'''''משפט:''''' יהיו <math>h \colon \Sigma \to \Delta^*</math> הומומורפיזם ו-<math>L \subseteq \Delta^*</math> שפה חסרת-הקשר. אז גם <math>h^{-1}(L)</math> חסרת-הקשר.

'''''רעיון ההוכחה:''''' לא ניתן את ההוכחה המלאה, אך ניתן את הרעיון הכללי ובנייה. תהי <math>L \subseteq \Delta^*</math> שפה חסרת הקשר. אז קיים [[אוטומט מחסנית]] <math>M = (Q,\Sigma,\Gamma,\delta,q_0,\dashv,F)</math> שמקבל אותה באמצעות מצבים מקבלים (כלומר <math>L_f(M) = L</math>). נבנה אוטומט מחסנית <math>M'</math> שמקבל את <math>h^{-1}(L)</math>, ולכן היא חסרת-הקשר. חשוב לשים לב שהאוטומט לא יכול לרוקן יותר מאות אחת מראש המחסנית בצעד אחד. לכן, בהינתן אות קלט <math>\sigma \in \Sigma</math>, <math>M'</math> לא תמיד יוכל לסמלץ את <math>M</math> עבור מילת הקלט <math>h(\sigma)</math> בצעד אחד. ואמנם, השימוש במסעי-<math>\varepsilon</math> יבוא לעזרנו. כלומר, האוטומט <math>M'</math> יקרא אות קלט <math>\sigma \in \Sigma</math>, יסמלץ את <math>M</math> עם מילת הקלט <math>h(\sigma)</math> בעזרת מסעי-<math>\varepsilon</math>, ואז יקרא עוד אות קלט ויפעל באופן זהה, עד אשר יסיים את קריאת המילה, ואז יגיע למצב מקבל.

נגדיר את מצבי <math>M'</math> להיות <math>Q' := Q \times \Delta'</math> כאשר <math>\Delta'</math> הוא אוסף כל המילים מעל <math>\Delta</math> באורך לכל היותר <math>\max\{|h(\sigma)| : \sigma \in \Sigma\}</math>, כלומר האורך המקסימלי שייתכן לתת מילת קלט כלשהו ש-<math>M'</math> יצטרך לסמלץ. כלומר, זוג <math>(q,w) \in Q'</math> מייצג מצב <math>q</math> בו <math>M</math> נמצא, ויתרת מילה <math>w</math> שעליו לקרוא. המצב ההתחלתי יהיה <math>q_0' := (q_0,\varepsilon)</math> (כי תחילה אין מילת קלט שעל <math>M</math> לקרוא). המצבים המקבלים יהיו <math>F' := F \times \{ \varepsilon\}</math> כי על <math>M</math> להגיע למצב מקבל, ואין עוד יתרת מילה שעליו לקרוא. אם כן, <math>M' = (Q',\Sigma,\Gamma,\delta',(q_0,\varepsilon),\dashv,F \times \{\varepsilon\})</math>.

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

1. קריאת אות קלט על ידי <math>M'</math>: {{ש}}
<math>\delta'((q,\varepsilon),\sigma,Z) := \{((q,h(\sigma)),Z)\}</math> לכל <math>q \in Q, \sigma \in \Sigma, Z \in \Gamma</math>.

2. סימולציית <math>M</math> - מסעי-<math>\varepsilon</math>: {{ש}}
<math>\delta'((q,\tau w),\varepsilon,Z) := \{((p,w),\alpha) : (p,\alpha) \in \delta(q,\tau,Z)\}</math> לכל <math>q \in Q, Z \in \Gamma, \tau \in \Delta \cup \{\varepsilon\}, w \in \Sigma^*</math> (אם <math>\tau \in \Delta</math> מסמלצים מעבר "רגיל" של <math>M</math>, ואם <math>\tau = \varepsilon</math> מסמלצים מסע-<math>\varepsilon</math> של <math>M</math>).

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

'''טענת עזר:''' לכל <math>q,p \in Q,\, w \in \Sigma^*,\, \alpha,\beta \in \Gamma^*</math>, אם <math>(q,h(w),\alpha) \vdash_M^* (p,\varepsilon,\beta)</math> אז <math>((q,\varepsilon),w,\alpha) \vdash_{M'}^* ((p,\varepsilon),\varepsilon,\beta)</math>.

כעת, כל שנותר להראות הוא ש-<math>L_f(M') = h^{-1}(L)</math>.

== לקריאה נוספת ==
* שמואל זקס ו[[נסים פרנסיז]], '''אוטומטים ושפות פורמליות''', [[האוניברסיטה הפתוחה]], 2001
* [https://gadial.net/2014/12/21/regular_languages_closure_2/ שפות רגולריות - תכונות סגור (חלק ב')] בבלוג "לא מדויק"

{{ערך יתום}}

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