שפות רגולריות - תכונות סגור (חלק ב')

בפוסט הקודם דיברתי על תכונות סגור יחסית סטנדרטיות של שפות רגולריות (עם החריג של פעולת סגור קלייני, שהייתי צריך לתת לה מוטיבציה מורכבת כלשהי). עכשיו בואו נעבור לתכונת סגור שונה לגמרי - הומומורפיזם. המילה הזו בטח מוכרת לכל מי שעשה קורס באלגברה מופשטת, וספציפית בתורת החבורות. הומומורפיזם בין שתי חבורות הוא פונקציה \( h:G\to H \) המקיימת \( h\left(ab\right)=h\left(a\right)h\left(b\right) \) - כלומר, היא מכבדת את פעולות הכפל של החבורות (או, אם תרצו, משמרת את המבנה של החבורה). מונואיד, אמרנו, הוא “כמעט כמו חבורה” ולכן אין מניעה להגדיר הומומורפיזמים בצורה זהה עבורו. אם כן, בהינתן שני אלפביתים \( \Sigma,\Delta \), נגדיר הומומורפיזם בתור פונקציה \( h:\Sigma^{*}\to\Delta^{*} \) שמקיימת \( h\left(uv\right)=h\left(u\right)h\left(v\right) \) לכל זוג מילים \( u,v\in\Sigma^{*} \).

חיש קל מתברר שאם \( h \) היא הומומורפיזם, אז מספיק לדעת את הערכים שלה על אברי \( \Sigma \) כדי לדעת מה היא תחזיר לכל איבר שהוא. הרי אם \( w=\sigma_{1}\dots\sigma_{n} \) היא מילה כלשהי, אז \( h\left(w\right)=h\left(\sigma_{1}\dots\sigma_{n}\right)=h\left(\sigma_{1}\right)\cdots h\left(\sigma_{n}\right) \). לכן זה האופן שבו מגדירים הומומורפיזם - פונקציה \( h:\Sigma\to\Delta^{*} \) שאחר כך כבר מורחבת באופן טבעי לכל \( \Sigma^{*} \). איבר אחד שאולי לא ברור לגמרי איך להרחיב את \( h \) עליו הוא המילה הריקה \( \varepsilon \); אבל מכיוון ש-\( h\left(\varepsilon\right)=h\left(\varepsilon\cdot\varepsilon\right)=h\left(\varepsilon\right)\cdot h\left(\varepsilon\right) \) הרי שמשיקולי אורך נטו (\( \left|h\left(\varepsilon\right)\right|=2\left|h\left(\varepsilon\right)\right| \)) כבר ברור שבהכרח \( h\left(\varepsilon\right)=\varepsilon \).

כעת, הטענה שלי היא שהומומורפיזם הוא תכונת סגור - דהיינו, שהתמונה של כל שפה רגולרית תחת הומומורפיזם היא שפה רגולרית. כזכור, מסמנים \( h\left(L\right)=\left\{ h\left(w\right)\ |\ w\in L\right\} \) (זה המושג הרגיל של תמונה של קבוצה תחת פונקציה). איך אני אוכיח שזו אכן תכונת סגור? ובכן, יש לי כעת כלי נשק חזק - אני מכיר את המבנה האינדוקטיבי של קבוצת השפות הרגולרית, וזה מאפשר לי להוכיח עליה דברים באינדוקציית מבנה. מספיק שאוכיח שהטענה נכונה עבור אברי הבסיס ושהיא משתמרת עבור פעולות היצירה.

אברי הבסיס של קבוצת השפות הרגולריות כוללים את \( \emptyset \) - וכמובן ש-\( h\left(\emptyset\right)=\emptyset \) ולכן התמונה של \( \emptyset \) רגולרית; כוללים את \( \left\{ \varepsilon\right\} \) וכמובן ש-\( h\left(\left\{ \varepsilon\right\} \right)=\left\{ \varepsilon\right\} \) רגולרית; וכוללים את \( \left\{ \sigma\right\} \) לכל \( \sigma\in\Sigma \) וכמובן ש-\( h\left(\left\{ \sigma\right\} \right)=\left\{ h\left(\sigma\right)\right\} \) רגולרית (כי סינגלטון הוא שפה סופית ולכן רגולרית). נשאר לטפל בפעולות היצירה.

ניקח אם כן שפות \( L_{1},L_{2} \) ונניח שהן רגולריות ושמתקיים שגם \( h\left(L_{1}\right),h\left(L_{2}\right) \) רגולריות. כעת שימו לב לכך ש-\( h\left(L_{1}\cup L_{2}\right)=h\left(L_{1}\right)\cup h\left(L_{2}\right) \) ומכאן שגם \( h\left(L_{1}\cup L_{2}\right) \) רגולרית; ושמתקיים \( h\left(L_{1}\cdot L_{2}\right)=h\left(L_{1}\right)\cdot h\left(L_{2}\right) \) ומכאן שגם \( h\left(L_{1}\cdot L_{2}\right) \) רגולרית; ושמתקיים \( h\left(L_{1}^{*}\right)=\left(h\left(L_{1}\right)\right)^{*} \) ולכן גם \( h\left(L_{1}^{*}\right) \) רגולרית - כלומר, פעולות היצירה משמרות את התכונה “\( h \) מעבירה שפה רגולרית לשפה רגולרית”. מן הסתם צריך להוכיח ה”שימו לב שמתקיים”-ים שלי אבל זה תרגיל טוב עבורכם.

את ההוכחה הזו ניתן להכליל בלי קושי גם עבור תכונת סגור יותר מופרעת - הצבה. הצבה דומה להומומורפיזם, רק שבמקום ש-\( h \) תחזיר מילה על כל אות, היא מחזירה שפה. השוויון \( h\left(w\right)=h\left(\sigma_{1}\right)\cdots h\left(\sigma_{n}\right) \) הוא עדיין בעל משמעות עבור הצבה שכזו שכן אנחנו יודעים לשרשר שפות, ולכן ברור איך הצבה מוגדרת למילים. ועבור שפות? \( h\left(L\right)=\bigcup_{w\in L}h\left(w\right) \).

כעת, ההוכחה עבור הומומורפיזם עוברת כמעט אחד-לאחד עבור הצבות. מה יכול להשתבש? בדיוק דבר אחד- \( h\left(\left\{ \sigma\right\} \right) \) אינו הסינגלטון \( \left\{ h\left(\sigma\right)\right\} \); הוא שפה כלשהי (הרי את \( h \) על \( \sigma \) ניתן להגדיר איך שבא לנו). אם כן, ברור מה הדרישה שאנחנו חייבים לדרוש - ש-\( h \) תחזיר לכל \( \sigma \) לא סתם שפה, אלא שפה רגולרית. להצבה שעושה את זה קוראים הצבה רגולרית ומה שראינו הוא שהצבה רגולרית שכזו היא תכונת סגור של שפות רגולריות.

הומומורפיזם הוא בעצם מקרה פרטי של הצבה שבו ההצבה מחזירה סינגלטון לכל אות. אז למה טרחתי לדבר על הומומורפיזם לבד? כי יש לי עניין גם במה שנקרא ההומומורפיזם ההפוך. באופן כללי, הומומורפיזם לא בהכרח יהיה חח”ע ועל, ולכן לא יהיה הפיך בתור פונקציה, אבל זה לא מונע מאיתנו לדבר על המקור של שפה כלשהי תחת ההומומורפיזם. פורמלית, אם \( h:\Sigma^{*}\to\Delta^{*} \) הוא הומומורפיזם, ו-\( L\subseteq\Delta^{*} \) אז מגדירים \( h^{-1}\left(L\right)\triangleq\left\{ w\in\Sigma^{*}\ |\ h\left(w\right)\in L\right\} \). כצפוי, אני רוצה לטעון שזו תכונת סגור, אבל בואו נראה קודם כל שימוש קלאסי בתכונת הסגור הזו כדי להבין למה היא כל כך מעניינת.

נניח ש-\( L \) היא שפה רגולרית מעל \( \Sigma \), ואני רוצה מסיבות השמורות עמי להתעסק עם השפה שמתקבלת מ-\( L \) על ידי לקיחת כל מילה ב-\( L \) מאורך זוגי והסרה של כל האותיות במקומות האי-זוגיים שלה. כלומר, אני רוצה לטפל בשפה \( \left\{ \sigma_{2}\sigma_{4}\dots\sigma_{2n}\ |\ \exists\sigma_{1},\dots,\sigma_{2n-1}:\sigma_{1}\sigma_{2}\dots\sigma_{2n}\in L\right\} \). איך אני מראה שהשפה הזו רגולרית? אפשר עם אוטומט מחוכם שמבצע סימולציה של האוטומט עבור \( L \) ו”מנחש” את האותיות במקומות האי-זוגיים, אבל יש דרך הרבה יותר פשוטה לקבל את השפה הזו מתוך \( L \) באמצעות תכונות סגור, מרגע שהתרגלנו כבר לעבוד עם תכונות הסגור הללו. מה שאני ארצה לעשות הוא לקחת את המילים של \( L \) שהן מאורך זוגי ולשים איכשהו סימון - “תג” - על כל אות במקום אי-זוגי. ואז להפעיל הומומורפיזם שמוחק את כל האותיות עם תגים ולא נוגע באחרות. עיקר העבודה כאן היא לבצע את התיוג הזה, ובשביל זה אשתמש בהומומורפיזם הפוך.

פורמלית, בואו ניקח את האלפבית \( \Sigma \) ונגדיר לו אלפבית מקביל של “אותיות עם תג” - \( \Sigma^{\prime}=\left\{ \sigma^{\prime}\ |\ \sigma\in\Sigma\right\} \). כעת, נגדיר הומומורפיזם \( h:\left(\Sigma\cup\Sigma^{\prime}\right)^{*}\to\Sigma^{*} \) שמוגדר באופן הבא: \( h\left(\sigma\right)=h\left(\sigma^{\prime}\right)=\sigma \). כלומר, ההומומורפיזם פשוט מסיר תגים מהמילה (מבלי למחוק את האותיות עם התגים!)

זה נראה כמו הומומורפיזם מטופש ולא מעניין, וזה נכון; מה שמעניין הוא ההומומורפיזם ההפוך. תחשבו על זה קצת ותראו ש-\( h^{-1}\left(L\right) \) הוא “כל המילים מתוך \( L \) כשכל מילה מופיעה עם כל קומבינציות התגים האפשריות עליה” (למשל: מתוייגת כולה; לא מתוייגת בכלל; כל מקום אי זוגי מתוייג; וכו’ וכו’).

כרגע יש יותר מדי תיוגים על המילים בשפה שקיבלנו, אבל זו לא בעיה - כדי להתמקד רק על התיוג שאנחנו רוצים, אפשר לבצע חיתוך עם שפה רגולרית אחרת: \( h^{-1}\left(L\right)\cap\left(\Sigma^{\prime}\Sigma\right)^{*} \) זו בדיוק שפת כל המילים מ-\( L \) שהן מאורך זוגי ומכילות תגים על המקומות האי זוגיים (למה השפה הימנית בחיתוך היא רגולרית? מתכונות הסגור שכבר ראינו).

כעת כל שנותר לעשות הוא להגדיר הומומורפיזם נוסף, \( g:\left(\Sigma\cup\Sigma^{\prime}\right)^{*}\to\Sigma^{*} \) על ידי \( g\left(\sigma\right)=\sigma \) ו-\( g\left(\sigma^{\prime}\right)=\varepsilon \). כלומר, הומומורפיזם שמוחק את האותיות המתוייגות. כעת \( g\left(h^{-1}\left(L\right)\cap\left(\Sigma^{\prime}\Sigma\right)^{*}\right) \) היא בדיוק השפה המבוקשת. תעלול התיוג הסטנדרטי פותר עוד תרגילים דומים בצורה נחמדה.

עכשיו בואו נראה שהומומורפיזם הפוך הוא תכונת סגור. אני אעשה את זה בדרך הסטנדרטית: אקח אוטומט \( A \) עבור השפה \( L \) ואבנה אוטומט \( A^{\prime} \) עבור \( h^{-1}\left(L\right) \). מכיוון שהבניה פשוטה בצורה קיצונית אני אציג אותה בצורה פורמלית. אבל קודם - הרעיון. יש לנו הומומורפיזם \( h:\Sigma\to\Delta \). יש לנו שפה \( L\subseteq\Delta^{*} \) (שימו לב - השפה לא מעל \( \Sigma^{*} \) כמו בדרך כלל). כעת אנו מקבלים מילה \( w\in\Sigma^{*} \) וצריכים לקבוע האם \( h\left(w\right)\in L \). איך נעשה את זה? מן הסתם, סימולציה של האוטומט \( A \) עבור השפה \( L \), אבל סימולציה שלו על מה? על הקלט \( h\left(w\right) \).

בואו נציג שניה את \( w \) כשרשור אותיות: \( w=\sigma_{1}\sigma_{2}\dots\sigma_{n} \). אז אנחנו יודעים ש-\( h\left(w\right)=h\left(\sigma_{1}\right)\dots h\left(\sigma_{n}\right) \). מכאן שהגיוני שהסימולציה שלנו תתנהל כך: קודם כל נקרא את \( \sigma_{1} \) מתוך הקלט האמיתי שלנו, ואז נבצע סימולציה של \( A \) על \( h\left(\sigma_{1}\right) \). אחר כך נקרא את \( \sigma_{2} \) ונמשיך את הסימולציה של \( A \), הפעם על \( h\left(\sigma_{2}\right) \) וכן הלאה. בסוף נקבל אם ורק אם \( A \) קיבלה. פשוט!

אם כן, פורמליזם. נסמן \( A=\left(\Delta,Q,q_{0},\delta,F\right) \), וכעת נבנה את האוטומט החדש שלנו, \( A^{\prime}=\left(\Sigma,Q,q_{0},\delta^{\prime},F\right) \) - אותם מצבים, אותו מצב התחלתי, אותם מצבים מקבלים. ההבדלים הם רק בא”ב, כמובן, ובפונקציית המעברים, שמוגדרת כך:

\( \delta^{\prime}\left(q,\sigma\right)=\hat{\delta}\left(q,h\left(\sigma\right)\right) \)

שימו לב שברמת הפורמליזם, אנחנו אפילו לא מבצעים סימולציה של \( A \) על \( h\left(\sigma\right) \) - אין לנו צורך ממש להריץ את \( A \) צעד צעד. אנחנו פשוט קופצים אוטומטית אל המצב שאליו \( A \) אמורה להגיע אחרי קריאת \( h\left(\sigma\right) \) - שזה מידע שאנחנו יכולים לבצע “אופליין”, לא כחלק מריצת האלגוריתם עצמו.

עדיין לא השתכנעתם שזה עובד? מצויין! הנה לכם תרגיל קל ונחמד - להוכיח שזה עובד. פורמלית.

לפני תכונת הסגור האחרונה שאני רוצה להציג, שיש בה עניין מוזר למדי, אני אקח הפסקה ואדבר על תכונה קלילה במיוחד - היפוך. בהינתן מילה \( w=\sigma_{1}\sigma_{2}\dots\sigma_{n} \), נגדיר את ההיפוך שלה באופן המתבקש - אותן האותיות אבל בסדר הפוך: \( w^{R}\triangleq\sigma_{n}\dots\sigma_{2}\sigma_{1} \). הקפיצה להיפוך של שפה היא מיידית: \( L^{R}=\left\{ w^{R}\ |\ w\in L\right\} \). הטענה היא שהיפוך של שפה רגולרית הוא עדיין שפה רגולרית. איך מוכיחים את זה? אם מדגדג לכם לומר “ניקח אוטומט עבור \( L \) ופשוט נהפוך את כיווני הקשתות”, אתם צודקים. מה שנחמד פה הוא שאם עושים את ההיפוך הזה על אוטומט סופי דטרמיניסטי, רוב הסיכויים שהאוטומט שתקבלו יהיה אי-דטרמיניסטי, אבל כבר ראינו שהמודלים שקולים אז אין עם זה בעיה (אבל זה רק ממחיש כמה חשוב היה לדבר על אוטומט אי-דטרמיניסטי לפני שהתחלנו לדבר על תכונות סגור).

נעבור לתכונה האחרונה, שנקראת “חלוקה” וקצת קשה להסביר אותה. הרעיון הוא כזה: קחו שתי שפות \( L_{1},L_{2} \). עכשיו, קחו מילה כלשהי מ-\( L_{1} \). תבדקו אם אפשר לפרק אותה לשני חלקים - רישא וסיפא (רישא - כל האותיות החל מתחילת המילה עד מקום מסויים; סיפא - כל האותיות החל ממקום מסויים במילה ועד סופה), באופן כזה שהסיפא שייכת ל-\( L_{2} \). אם כן, זרקו את הרישא לסל. התוצאה של פעולת החלוקה היא כל המילים שנכנסות כך לסל. פורמלית:

\( L_{1}/L_{2}\triangleq\left\{ x\in\Sigma^{*}\ |\ \exists y\in L_{2}:xy\in L_{1}\right\} \)

הפעולה הזו נקראת חלוקה מימין כי \( y \) הוא בחלק הימני של המילה. אבל יש גם חלוקה משמאל:

\( L_{2}\backslash L_{1}\triangleq\left\{ x\in\Sigma^{*}\ |\ \exists y\in L_{2}:yx\in L_{1}\right\} \)

אני אדבר רק על חלוקה מימין, כי חלוקה משמאל אפשר לקבל באמצעות היפוך: \( L_{2}\backslash L_{1}=\left(L_{1}^{R}/L_{2}^{R}\right)^{R} \).

על פניו, אפשר להוכיח שחלוקה מימין היא תכונת סגור באמצעות מה שכבר ראינו. נניח ש-\( L_{1},L_{2} \) רגולריות. נשתמש בתיוג בעזרת הומומורפיזם הפוך על \( L_{1} \) ונחתוך עם השפה \( \Sigma^{*}L_{2}^{\prime} \) (כל המילים שמורכבות מרישא לא מתוייגת כלשהי ומסיפא מתוייגת ב-\( L_{2} \)). נפעיל על התוצאה הומומורפיזם שמוחק אותיות עם תגים, וסיימנו. אז למה בעצם אני מדבר על התכונה הזו בנפרד ולמה אני אומר שיש איתה “עניין מוזר במיוחד”? ובכן, כי אני יכול לעשות יותר ממה שכבר תיארתי - אני טוען שכל עוד \( L_{1} \) היא רגולרית, אז החלוקה שלה ב-\( L_{2} \) תהיה רגולרית - מבלי שאצטרך את זה ש-\( L_{2} \) תהיה רגולרית. \( L_{2} \) יכולה להיות כל שפה שהיא, כולל שפות שהן בכלל לא כריעות (כלומר, אין אלגוריתם שיודע לקבוע, בהינתן מילה, אם היא בשפה או לא - למשל, בעיית העצירה).

אז מה עושים? נניח ש-\( A=\left(\Sigma,Q,q_{0},\delta,F\right) \) הוא אוטומט עבור \( L_{1} \). נבנה אוטומט \( A^{\prime} \) עבור \( L_{1}/L_{2} \). הרעיון, כרגיל, יהיה לבצע סימולציה של \( A \); אנחנו קוראים מילה \( x \) ומסמלצים עליה את \( A \). האקשן מגיע כש-\( x \) נגמרת. בשלב הזה אנחנו עוצרים ושואלים את עצמנו - האם קיימת איזו שהיא \( y\in L_{2} \) שאני יכול לקרוא החל מהמקום שהגעתי אליו ולסיים במצב מקבל?

אם \( L_{2} \) היא שפה מסובכת, אז לענות לשאלה הזו זה דבר קשה עד בלתי אפשרי. אבל, וזה קטע מבלבל אז תשארו איתי - לשאלה הזו קיימת תשובה גם אם אנחנו לא יודעים אותה, ומכך נובע שקיים אוטומט \( A^{\prime} \) שמתאים לשפת החלוקה גם אם אנחנו לא יודעים מהו.

לפני שתספיקו להתלונן, הנה האוטומט, פורמלית: \( A^{\prime}=\left(\Sigma,Q,q_{0},\delta,F^{\prime}\right) \). כלומר: אותה קבוצת מצבים, אותו מצב התחלתי ואותה פונקציית מעברים כמו של \( A \). ההבדל היחיד הוא קבוצת המצבים המקבלים, שמוגדרת כך:

\( F^{\prime}=\left\{ q\in Q\ |\ \exists y\in L_{2}:\hat{\delta}\left(q,y\right)\in F\right\} \)

אין ויכוח על כך שמבחינה מתמטית \( F^{\prime} \) קיימת, ושהיא באמת מוגדרת היטב - כלומר, עבור כל \( q\in Q \) ההגדרה לא מאפשרת לו להיות בו זמנית בתוך ומחוץ ל-\( F^{\prime} \). העניין הוא שלא תמיד תהיה לנו יכולת למצוא אלגוריתמית את \( F \). אבל כל העניין הוא שזה לא באמת חשוב: כדי להראות ששפה היא רגולרית אנחנו לא צריכים למצוא אוטומט עבור השפה שלה, רק להראות שאוטומט כזה קיים. והוכחה פורמלית קצרה תראה ש-\( F^{\prime} \) שנתתי אכן גורמת לכך ש-\( L\left(A^{\prime}\right)=L_{1}/L_{2} \).

כהערת אגב, כל שאר תכונות הסגור שהראיתי כאן כן היו קונסטרוקיטיביות, כלומר בהינתן אוטומטים עבור השפות שמתחילים מהן, אני יודע איך לבנות אוטומטים עבור השפות שמתקבלות מפעולות הסגור. יוצאת מן הכלל אחת היא פעולת ההצבה, שבהוכחה עבורה הסתמכתי על כך שאני יודע לתאר כל שפה רגולרית באמצעות פעולות החיבור-שרשור-סגור קלייני מתוך שפות הבסיס (ריקה והסינגלטונים). זה ה”חוב” שנשאר לי, ובפוסט הזה אשלם אותו בשמחה, כי ההוכחה שאראה (שאינה קשה בצורה חריגה אבל יש בה רעיון אחד מבריק) היא אחד מהדברים החביבים עלי בנושא הזה.