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

בתורת השפות הפורמליות, הומומורפיזם הוא פונקציה המעבירה אותיות מא"ב אחד למילים מעל א"ב אחר. באופן פורמלי, בהינתן $\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 )$ .