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

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

הרחבות

נוכל להרחיב את מושג ההומומורפיזם למילים ואף לשפות. יהיו $\mathrm{\Sigma },\mathrm{\Delta }$ שני א"ב ויהי הומומורפיזם $h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{*}$.

• ההרחבה למילים של $h$ היא פונקציה $\hat{h}:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Delta }}^{*}$ (כלומר, מעבירה מילים מעל $\mathrm{\Sigma }$ למילים מעל $\mathrm{\Delta }$) המוגדרת באופן הבא: תבנית:ש $\begin{array}{cc}\hat{h}(\epsilon )& :=\epsilon \\ \hat{h}(w\sigma )& :=\hat{h}(w)\cdot h(\sigma )\end{array}$ תבנית:ש נשים לב שנובע שאם $w={\sigma }_1{\sigma }_2\dots {\sigma }_n\in {\mathrm{\Sigma }}^{*}$ אז מההגדרה $\hat{h}(w)=h({\sigma }_1)h({\sigma }_2)\dots h({\sigma }_n)$, כלומר זהו שרשור המילים אליהן הועתקו אותיות המילה $w$ על ידי $h$ (וכן נובעת הטענה השימושית כי לכל $w_1,w_2\in {\mathrm{\Sigma }}^{*}$ מתקיים $\hat{h}(w_1{w}_2)=\hat{h}(w_1)\cdot \hat{h}(w_2)$). אם לכל $\epsilon \ne w\in {\mathrm{\Sigma }}^{*}$ (כאשר $\epsilon$ המילה הריקה) מתקיים $h(w)\ne \epsilon$ אז נאמר ש-$\hat{h}$ היא $\mathit{\epsilon }$-חופשית.
• ההרחבה לשפות של $h$ היא פונקציה $\hat{\hat{h}}:2^{{\mathrm{\Sigma }}^{*}}\to 2^{{\mathrm{\Delta }}^{*}}$ (כלומר, מעבירה שפות מעל $\mathrm{\Sigma }$ לשפות מעל $\mathrm{\Delta }$) המוגדרת: תבנית:ש $\hat{\hat{h}}(L):=\{\hat{h}(w):w\in L\}$ לכל שפה $L\subseteq {\mathrm{\Sigma }}^{*}$.

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

דוגמה

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

$h(a)=012,h(b)=21$.

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

$\hat{h}(bba)=h(b)h(b)h(a)=2121012$.

נעיין בשפה $L=\{a^i{b}^j:i,j\ge 0\}$. אז

$\hat{\hat{h}}(L)=\{\hat{h}(a^i{b}^j):i,j\ge 0\}=\{(h(a){)}^i(h(b){)}^j:i,j\ge 0\}=\{(012{)}^i(21{)}^j:i,j\ge 0\}$.

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

משפחת השפות הרגולריות סגורה תחת הומומורפיזם. כלומר, בהינתן $L\subseteq {\mathrm{\Sigma }}^{*}$ רגולריות ו-$h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{*}$ הומומורפיזם, השפה $h(L)\subseteq {\mathrm{\Delta }}^{*}$ גם רגולרית.

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

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

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

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

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

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

$h^{-1}(L)=\{w\in {\mathrm{\Sigma }}^{*}:h(w)\in L\}$ לכל $L\subseteq {\mathrm{\Delta }}^{*}$. כלומר כעת, $h^{-1}$ מעבירה כל שפה מעל $\mathrm{\Delta }$ לשפה מעל $\mathrm{\Sigma }$. נעיר שבאופן שקול יכולנו גם להגדיר $h^{-1}(L)=\bigcup _{w\in L}{h}^{-1}(w)$.

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

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

משפט: יהיו $h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{*}$ הומומורפיזם ו-$L\subseteq {\mathrm{\Delta }}^{*}$ שפה רגולרית. אז גם $h^{-1}(L)$ רגולרית.

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

רעיון הבניה הוא כדלהלן: בהינתן $w\in {\mathrm{\Sigma }}^{*}$, על מנת לקבוע את שייכותה ל-$h^{-1}(L)$, נרצה להפעיל סימולציה של $A$ על $h(w)$ כדי לקבוע את שייכותה ל-$L$ (וזה יהיה אופן פעילות $A^{\prime }$). אז אם $w={\sigma }_1{\sigma }_2\dots {\sigma }_n$, נרצה לבדוק האם $h(w)=h({\sigma }_1)h({\sigma }_2)\dots h({\sigma }_n)\in L$. נרצה אם כן, שכאשר האוטומט $A^{\prime }$ נמצא במצב $q\in Q$ ומקבל אות קלט $\sigma \in \mathrm{\Sigma }$, הוא "יפעיל" סימולציה של $A$ מהמצב $q$ עם מילת הקלט $h(\sigma )$.

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

טענת עזר: מתקיים $\widehat{{\delta }^{\prime }}(q_0,w)=\hat{\delta }(q_0,h(w))$ לכל $w\in {\mathrm{\Sigma }}^{*}$.

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

בסיס: אם $w=\epsilon$ נקבל כי

$\widehat{{\delta }^{\prime }}(q_0,\epsilon )=q_0=\hat{\delta }(q_0,\epsilon )=\delta (q_0,h(\epsilon ))$

מהגדרת פונקציית המעברים המורחבת וכן מהגדרת ההומומורפיזם. למילים באורך $1$ הטענה מתקיימת ישירות מהגדרתנו ל-${\delta }^{\prime }$.

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

$\widehat{{\delta }^{\prime }}(q_0,w)=\widehat{{\delta }^{\prime }}(q_0,u\sigma )={\delta }^{\prime }(\widehat{{\delta }^{\prime }}(q_0,u),\sigma )={\delta }^{\prime }(\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 }^{\prime }$; מעבר (5) הוא מהטענה $\hat{\delta }(\hat{\delta }(q,w_1),w_2)=\hat{\delta }(q,w_1{w}_2)$; מעבר (6) הוא מהגדרת ההומומורפיזם). $◼$

נמשיך בהוכחה. נראה ש-$L(A^{\prime })=h^{-1}(L)$. אכן

$w\in L(A^{\prime })\iff \widehat{{\delta }^{\prime }}(q_0,w)\in F\iff \hat{\delta }(q_0,h(w))\in F\iff h(w)\in L\iff w\in h^{-1}(L)$

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

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

משפט: יהיו $h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{*}$ הומומורפיזם ו-$L\subseteq {\mathrm{\Delta }}^{*}$ שפה חסרת-הקשר. אז גם $h^{-1}(L)$ חסרת-הקשר.

רעיון ההוכחה: לא ניתן את ההוכחה המלאה, אך ניתן את הרעיון הכללי ובנייה. תהי $L\subseteq {\mathrm{\Delta }}^{*}$ שפה חסרת הקשר. אז קיים אוטומט מחסנית $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,⊣,F)$ שמקבל אותה באמצעות מצבים מקבלים (כלומר $L_f(M)=L$). נבנה אוטומט מחסנית $M^{\prime }$ שמקבל את $h^{-1}(L)$, ולכן היא חסרת-הקשר. חשוב לשים לב שהאוטומט לא יכול לרוקן יותר מאות אחת מראש המחסנית בצעד אחד. לכן, בהינתן אות קלט $\sigma \in \mathrm{\Sigma }$, $M^{\prime }$ לא תמיד יוכל לסמלץ את $M$ עבור מילת הקלט $h(\sigma )$ בצעד אחד. ואמנם, השימוש במסעי-$\epsilon$ יבוא לעזרנו. כלומר, האוטומט $M^{\prime }$ יקרא אות קלט $\sigma \in \mathrm{\Sigma }$, יסמלץ את $M$ עם מילת הקלט $h(\sigma )$ בעזרת מסעי-$\epsilon$, ואז יקרא עוד אות קלט ויפעל באופן זהה, עד אשר יסיים את קריאת המילה, ואז יגיע למצב מקבל.

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

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

1. קריאת אות קלט על ידי $M^{\prime }$: תבנית:ש ${\delta }^{\prime }((q,\epsilon ),\sigma ,Z):=\{((q,h(\sigma )),Z)\}$ לכל $q\in Q,\sigma \in \mathrm{\Sigma },Z\in \mathrm{\Gamma }$.

2. סימולציית $M$ - מסעי-$\epsilon$: תבנית:ש ${\delta }^{\prime }((q,\tau w),\epsilon ,Z):=\{((p,w),\alpha ):(p,\alpha )\in \delta (q,\tau ,Z)\}$ לכל $q\in Q,Z\in \mathrm{\Gamma },\tau \in \mathrm{\Delta }\cup \{\epsilon \},w\in {\mathrm{\Sigma }}^{*}$ (אם $\tau \in \mathrm{\Delta }$ מסמלצים מעבר "רגיל" של $M$, ואם $\tau =\epsilon$ מסמלצים מסע-$\epsilon$ של $M$).

זו בדיוק הבנייה שעונה לתיאור שנתנו. להמשך ההוכחה הפורמלית, כדאי להוכיח את טענת העזר הבאה, שמשקפת את אופן פעולת $M^{\prime }$ כפי שתיארנו:

טענת עזר: לכל $q,p\in Q,w\in {\mathrm{\Sigma }}^{*},\alpha ,\beta \in {\mathrm{\Gamma }}^{*}$, אם $(q,h(w),\alpha )\underset{M}{\overset{*}{⊢}}(p,\epsilon ,\beta )$ אז $((q,\epsilon ),w,\alpha )\underset{M^{\prime }}{\overset{*}{⊢}}((p,\epsilon ),\epsilon ,\beta )$.

כעת, כל שנותר להראות הוא ש-$L_f(M^{\prime })=h^{-1}(L)$.

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 2001
• שפות רגולריות - תכונות סגור (חלק ב') בבלוג "לא מדויק"