שפות רגולריות - משפט קלייני

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

בפוסט הזה אני רוצה להוכיח את הטענה הזו בצורה פורמלית יחסית. בואו נתחיל.

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

קבוצת שפות הבסיס שלי, אם כן, היא הקבוצה הבאה: $latex \left\{ \emptyset,\left\{ \varepsilon\right\} \right\} \cup\left\{ \left\{ \sigma\right\} \ |\ \sigma\in\Sigma\right\} $. דהיינו, השפה הריקה, השפה שהאיבר היחיד שלה הוא המילה הריקה, והשפה שהאיבר היחיד שלה הוא המילה מאורך 1 $latex \sigma$, לכל אות $latex \sigma\in\Sigma$.

מבין פעולות הסגור, איחוד שפות זו פשוט פעולת האיחוד הרגילה של קבוצות. שרשור של שפות הוגדר להיות $latex L_{1}\cdot L_{2}\triangleq\left\{ w_{1}w_{2}\ |\ w_{1}\in L_{1},w_{2}\in L_{2}\right\} $ (כששרשור של מילים מוגדר בצורה הרגילה - המילה שמתקבלת מ”הדבקת” שתי המילים על פי הסדר שלהן). סגור-קלייני היה הפעולה המסובכת ביותר והפחות טבעית מבין הפעולות: $latex L^{*}\triangleq\bigcup_{n=0}^{\infty}L^{n}$, כאשר חזקה של שפות מוגדרת באופן הטבעי: $latex L^{0}\triangleq\left\{ \varepsilon\right\} $ ו-$latex L^{n+1}\triangleq L^{n}\cdot L$. כזכור, הגדרתי את סגור-קליניי מלכתחילה כי הייתה לי “אינטואיציה” שזו הפעולה שאזדקק לה כדי להוכיח את משפט קלייני. מה שיהיה נחמד בהוכחה (בין היתר) הוא שנבין בדיוק למה צריך דווקא את הפעולה הזו.

המשפט אומר שקבוצת השפות הרגולריות היא הקבוצה שנוצרת אינדוקטיבית מהבסיס ופעולות היצירה הללו. לא חייבים להבין מה זו קבוצה נוצרת אינדוקטיבית, אבל זה לא יזיק אז אקדיש לכך כמה פסקאות ואפשר לדלג אם רוצים. הרעיון הוא שזו הקבוצה הקטנה ביותר שמכילה את הבסיס וסגורה לפעולות היצירה. באופן כללי, אם יש לי “עולם” $latex X$, קבוצת בסיס $latex B\subseteq X$ וקבוצה $latex F$ של פעולות יצירה שהן פונקציות מהצורה $latex f:X^{n}\to X$ (כלומר, פונקציות שמקבלות $latex n$ קלטים, כאשר $latex n$ יכול להיות מספר טבעי חיובי כלשהו), אז אסמן ב-$latex X_{B,F}$ את הקבוצה הקטנה ביותר כך ש-$latex B\subseteq X_{B,F}$ ולכל $latex f\in F$ מתקיים ש-$latex f\left(X_{B,F}\right)\subseteq X_{B,F}$ (הסימון “$latex f\left(D\right)$” לקבוצה $latex D$ כלשהו פירושו כל הפלטים שמקבלים כאשר מציבים ב-$latex f$ את כל הקומבינציות האפשריות של איברים ב-$latex D$; הסיבה שאני בכלל טורח לומר זאת במפורש היא שאם $latex f$ היא פונקציה שמקבלת כמה קלטים, יכול להיראות לחלקכם מוזר שפתאום אני מכניס לה את ה”קלט” $latex D$. זה לא באמת קלט; זה סימון של התמונה של $latex f$).

עכשיו, תשאלו, למה הקבוצה הזו בכלל קיימת? ובכן, הנה טענה חביבה: $latex X_{B,F}=\bigcap\left\{ D\subseteq X\ |\ B\subseteq D\wedge\forall f\in F:f\left(D\right)\subseteq D\right\} $. במילים: $latex X_{B,F}$ מתקבלת מחיתוך כל הקבוצות שמכילות את $latex B$ וסגורות תחת $latex F$. זו דרך סטנדרטית במתמטיקה להגדיר אובייקטים “הכי קטנים” שכאלו באמצעות חיתוך מסוג זה. חשוב לשים לב לכך שהחיתוך לא נלקח מעל קבוצה ריקה של אובייקטים; $latex X$ עצמו תמיד נכלל כאיבר בחיתוך. לכן החיתוך מוגדר היטב, ולא קשה להוכיח שהוא אכן שווה ל-$latex X_{B,F}$.

מה שנחמד ב-$latex X_{B,F}$ הוא שקל להוכיח עליה טענות באינדוקציה: מוכיחים שמשהו מתקיים עבור $latex B$ ומשתמר עבור כל $latex f\in F$ ומקבלים שאותו משהו מתקיים לכל $latex X_{B,F}$. בעזרת אינדוקציית מבנה שכזו אפשר להוכיח, למשל, שאיבר כלשהו שייך ל-$latex X_{B,F}$ אם ורק אם קיימת לו סדרת יצירה - סדרה סופית שכל איבר בה הוא או איבר של $latex B$ או מתקבל מאיברים קודמים בסדרה על ידי הפעלת $latex f$, והאיבר האחרון בה הוא האיבר שהסדרה “יוצרת”. אולי לחלקכם זה מזכיר את האופן שבו מתוארות הוכחות במתמטיקה - סדרה של טענות כך שכל טענה היא אקסיומה או הנחה או נובעת מקודמותיה על ידי כלל היסק. זה כמובן לא מקרי - אפשר להגדיר את “קבוצת המשפטים היכיחים” (מאקסיומות/הנחות נתונות ועם כללי היסק נתונים) בדיוק בתור קבוצה אינדוקטיבית שכזו.

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

אם כן, הבה וניקח אוטומט סופי דטרמיניסטי כלשהו, $latex A=\left(\Sigma,Q,q_{1},\delta,F\right)$. אני מסמן את מצבי האוטומט בתור $latex Q=\left\{ q_{1},q_{2},\dots,q_{n}\right\} $. שימו לב שאני בוחר הפעם לסמן את המצב ההתחלתי של האוטומט ב-$latex q_{1}$ במקום ב-$latex q_{0}$ כרגיל; הסיבה לכך תתברר בהמשך אבל היא לא משהו קריטי - זה פשוט יפשט קצת סימון אחר שאציג עוד מעט.

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

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

אז אני יכול לנסות ולהגדיר שפות באופן הבא: לכל זוג מצבים $latex q,p\in Q$ נגדיר $latex L_{q,p}=\left\{ w\in\Sigma^{*}\ |\ \hat{\delta}\left(q,w\right)=p\right\} $ - שפת כל המילים שמעבירות את האוטומט מ-$latex q$ אל $latex p$. אם נצליח לבנות את השפות הללו, בבירור סיימנו, כי $latex L\left(A\right)=\bigcup_{p\in F}L_{q_{0},p}$ (שפת האוטומט היא אוסף כל המילים שמעבירות את האוטומט מהמצב ההתחלתי $latex q_{0}$ אל מצב מקבל כלשהו $latex p\in F$). אז מה הבעיה? שאין לי מושג איך לבנות את $latex L_{q,p}$, מן הסתם. זו עדיין שפה מסובכת, אפילו אם היא אולי פחות מסובכת מ”כל המילים שהאוטומט מקבל”.

אם השתמשתי בטריק של “לעבור מהשפה הקשה $latex L\left(A\right)$ לאיחוד של שפות יותר פשוטות מהצורה $latex L_{q,p}$” אולי אפשר לעשות את התעלול הזה שוב? אני אוטומטית חושב על כך שאפשר לפרק את $latex L_{q,p}$ על פי אורך המילים. כלומר, אסמן $latex L_{q,p}^{k}\triangleq\left\{ w\in L_{q,p}\ |\ \left|w\right|=k\right\} $ ואז $latex L_{q,p}=\bigcup_{k=0}^{\infty}L_{q,p}^{k}$. על פניו זה רעיון די טוב, כי אני יכול לתאר את $latex L_{q,p}^{k}$ באופן אינדוקטיבי על פי פירוק לפי הצעד האחרון: $latex L_{q,p}^{k}=\bigcup_{i=1}^{n}\left\{ w\sigma\ |\ w\in L_{q,q_{i}}^{k-1}\wedge\delta\left(q_{i},\sigma\right)=p\right\} $. במילים: $latex L_{q,p}^{k}$ כוללת את כל המילים מהצורה $latex w\sigma$ כך ש-$latex w$ היא מאורך $latex k-1$ ומעבירה את האוטומט מ-$latex q$ אל מצב $latex q_{i}$ כלשהו, ואילו $latex \sigma$ מעבירה אותנו מ-$latex q_{i}$ אל $latex p$.

זה לא עובד. זה רעיון נחמד, אבל זה לא עובד. לא בגלל שזה לא נכון, אלא בגלל המשוואה הזו: $latex L_{q,p}=\bigcup_{k=0}^{\infty}L_{q,p}^{k}$. כתבתי בכוונה את המשוואה הזו בצורה מטעה. אם נלך על פי ההגדרות היבשות שנתתי קודם, הרי ש-$latex \bigcup_{k=0}^{\infty}L_{q,p}^{k}$ היא בעצם $latex L_{p,q}^{*}$ וזה כמובן לא נכון, כי ה-$latex k$ שמופיע ב-$latex L_{q,p}^{k}$ הוא לא חזקה של שפה - הוא בסך הכל חלק מהסימון שאני משתמש בו. אני בכוונה מנסה להטעות אתכם ככה כדי להכריח אתכם לחשוב קצת ולהבין מה השתבש כאן. זה חשוב.

אם כן, המשוואה $latex L_{q,p}=\bigcup_{k=0}^{\infty}L_{q,p}^{k}$ היא אמנם נכונה לגמרי, אבל היא מציגה את $latex L_{q,p}$ בתור איחוד אינסופי של שפות - ואיחוד אינסופי שכזה הוא לא בהכרח רגולרי גם אם השפות המעורבות רגולריות. לכן כל הגישה שלנו של לפרק את $latex L_{q,p}$ על פי אורך המילה נידונה לכישלון - אורכי המילים הם לא חסומים ולכן בהכרח נקבל איחודים אינסופיים בעייתיים.

אז חזרה אל שולחן השרטוט ואל השאלה הבסיסית שלנו - מה כן חסום כאן? והתשובה ברורה - מספר המצבים של האוטומט $latex A$, שהוא בדיוק $latex n$. אבל איך אפשר להשתמש בזה כדי לפשט את $latex L_{q,p}$?

אנחנו רוצים איכשהו להגביל את המילים ב-$latex L_{q,p}$ ולקחת רק חלק מהן. קודם הגבלנו על פי אורך. עכשיו אני רוצה להגביל איכשהו על פי מצבי האוטומט. אני יודע שהמילים ב-$latex L_{q,p}$ מעבירות את האוטומט מ-$latex q$ אל $latex p$, אז איך שאר מצבי האוטומט יכולים להיכנס לתמונה? מתי הם רלוונטיים? ובכן, בדיוק כשאנחנו מסתכלים על המסלול שמעביר אותנו מ-$latex q$ אל $latex p$. אם אני רוצה להגביל, מה אני יכול לעשות? לי נראה ברור (כי ברור שהכל נראה לי ברור בדיעבד, כשאני כבר מכיר את ההוכחה…) שהדרך הנכונה להגביל היא לאסור על מעבר במצבים מסויימים. אפשר להמשיך עם המשחק הזה עוד קצת, אבל אני מאמין שמכאן ועד להגדרה הנכונה זה בעיקר ניסוי וטעיה וגישוש, אז הנה אתן את ההגדרה המרכזית כאן, שפותרת את הכל:

אני אגדיר את $latex L_{q,p}^{k}$ (כאשר שוב, ה-$latex k$ הזה הוא לא חזקה, הוא סתם סימון) להיות שפת כל המילים שמעבירות את האוטומט מ-$latex q$ אל $latex p$, באופן כזה שהמסלול מ-$latex q$ אל $latex p$ לא עובר באף מצב שהאינדקס שלו גדול מ-$latex k$. דגש על המילה עובר: האוטומט יכול להתחיל או לסיים את המסלול במצב שהאינדקס שלו גדול מ-$latex k$. כלומר, מותר ל-$latex q$ או $latex p$ עצמם להיות בעלי אינדקס גדול מ-$latex k$, כל עוד הם מופיעים רק בהתחלה ובסוף ולא בתוך המסלול בעצמם.

ומכיוון שאי אפשר רק עם הגדרה מילולית, הנה הגדרה פורמלית:

$latex L_{q,p}^{k}\triangleq\left\{ w\in\Sigma^{*}\ |\ \hat{\delta}\left(q,w\right)=p\wedge\forall u\ne\varepsilon,w:w=uv\wedge\hat{\delta}\left(q,u\right)=q_{i}\Rightarrow i\le k\right\} $

ההגדרה הזו אומרת - כל המילים $latex w\in\Sigma^{*}$ כך שקודם כל, $latex w$ מעבירה את האוטומט מ-$latex q$ אל $latex p$; וחוץ מזה, לכל פירוק $latex w=uv$ לא טריוויאלי (כלומר, ש-$latex u$ היא לא ריקה או לא כל $latex w$), המצב שאליו מגיעים מ-$latex q$ אחרי קריאת $latex u$ הוא בעל אינדקס קטן או שווה ל-$latex k$.

זהו זה. ההגדרה הזו פותרת את הכל. עד כדי כך שאני ממליץ לכם לא לנסות להמשיך לקרוא את ההוכחה אלא לנסות להמשיך להוכיח בעצמכם לפי שתיגשו לקרוא את המשך ההוכחה שלי.

המשך ההוכחה הוא זה: אני הולך להוכיח באופן אינדוקטיבי שכל השפות $latex L_{q,p}^{k}$ הן נוצרות אינדוקטיבית מקבוצות הבסיס באמצעות פעולות הסגור (עבור $latex p,q\in Q$ כלשהם ו-$latex 0\le k\le n$). זה יסיים את ההוכחה בגלל שברור לחלוטין ש-$latex L_{q,p}^{n}=L_{q,p}$ (כי אם המגבלה שלנו על המילים ב-$latex L_{q,p}$ היא “בקריאה שלכן אסור לעבור במצב עם אינדקס גדול מ-$latex n$” והאינדקס הגדול ביותר של מצב באוטומט הוא $latex n$, אין מגבלה). האינדוקציה תהיה על $latex k$.

נתחיל מ-$latex k=0$. במקרה הזה, $latex L_{q,p}^{k}$ היא שפה מוגבלת במיוחד. מכיוון שבחרתי שהאינדקס של מצב באוטומט שלי יתחיל מ-1 (וזו הסיבה שבגללה בחרתי את הבחירה הזו, אחרת הייתי צריך להתחיל מ-$latex k=-1$) הרי ש-$latex L_{q,p}^{0}$ היא שפת כל המילים $latex w$ שקריאתן מעבירה את $latex q$ ל-$latex p$ בלי מצבי ביניים בכלל. כלומר, מעבירה בלכל היותר צעד אחד. זה מראה מייד ש-$latex L_{q,p}^{0}$ היא איחוד סופי של שפות בסיס שלנו, או שהיא $latex \emptyset$ שגם היא שפת בסיס. אבל אני ארחיב קצת עבור מי שלא רואה את זה.

ראשית, שימו לב לכך ש-$latex q=p$ אם ורק אם $latex \varepsilon\in L_{q,p}^{0}$ (כי $latex \hat{\delta}\left(q,\varepsilon\right)=q$ - כך זה הוגדר). כמו כן, לכל $latex \sigma\in\Sigma$ מתקיים ש-$latex \delta\left(q,\sigma\right)=p$ אם ורק אם $latex \sigma\in L_{q,p}^{0}$. זה אומר שאפשר לכתוב את השפה שלנו בקיצור בתור:

$latex L_{q,p}^{0}=\left\{ \tau\in\Sigma\cup\left\{ \varepsilon\right\} \ |\ \hat{\delta}\left(q,\tau\right)=p\right\} =\bigcup_{\hat{\delta}\left(q,\tau\right)=p}\left\{ \tau\right\} $

מכיוון ש-$latex \tau\in\Sigma\cup\left\{ \varepsilon\right\} $, כל שפה מהצורה $latex \left\{ \tau\right\} $ היא אחת משפות הבסיס שלנו. ואם יוצא ש-$latex L_{q,p}^{0}=\emptyset$ גם זה בסדר כי גם $latex \emptyset$ היא אחת משפות הבסיס שלנו. וזה כמובן לא מקרי - זו הסיבה שבגללה בחרנו את שפות הבסיס הללו.

סיימנו עם בסיס האינדוקציה שלנו. כעת לאקשן האמיתי: נניח שכל השפות $latex L_{q,p}^{k-1}$ עבור $latex q,p\in Q$ כלשהם הן אינדוקטיביות (נוצרו מקבוצות הבסיס על ידי פעולות הסגור) ונוכיח ש-$latex L_{q,p}^{k}$ הן כאלו. כלומר, ניקח $latex q,p\in Q$ כלשהם ונראה איך אפשר “לבנות” את $latex L_{q,p}^{k}$ מתוך שפות עם $latex k-1$ למעלה, בעזרת פעולות הסגור.

נתחיל בשאלה המתבקשת - מה ההבדל בין $latex L_{q,p}^{k}$ ובין $latex L_{q,p}^{k-1}$? ברור ש-$latex L_{q,p}^{k-1}\subseteq L_{q,p}^{k}$; רק צריך להבין מי המילים ב-$latex L_{q,p}^{k}$ שלא נמצאות ב-$latex L_{q,p}^{k-1}$. על פי הגדרה, אלו כל המילים שלא עוברות באף מצב ביניים עם אינדקס גדול מ-$latex k$, אבל כן עוברות במצב ביניים עם אינדקס גדול מ-$latex k-1$ - כלומר, אלו בדיוק המילים שעוברות במצב $latex q_{k}$ לפחות פעם אחת.

עכשיו, בואו נניח ש-$latex w\in L_{q,p}^{k}$ היא מילה שמעבירה את $latex q$ ל-$latex p$ ועוברת ב-$latex q_{k}$ בדיוק פעם אחת (ובשאר הזמן היא עוברת רק במצבים עם אינדקס קטן יותר). זה אומר שאפשר לפרק אותה כך - $latex w=uv$ כך ש-$latex u$ מעבירה את $latex q$ אל $latex q_{k}$ ואילו $latex v$ מעבירה את $latex q_{k}$ אל $latex p$, ובשני המקרים הללו לא עוברים במצב ביניים עם אינדקס גדול מ-$latex k-1$ - כי בכל $latex w$ לא עוברים במצב ביניים עם אינדקס גדול מ-$latex k$, וכי בתוך הריצה של $latex u$ ושל $latex v$ לא מופיע $latex q_{k}$, אלא רק בקצוות של הריצה הזו (בסיום הריצה על $latex u$ ובתחילת הריצה על $latex v$. מכאן ש-$latex v\in L_{q,q_{k}}^{k-1}$ ואילו $latex u\in L_{q_{k},p}^{k-1}$.

המקרה הזה היה פשוט יחסית. בואו נעבור לרמת הסיבוך הבאה: נניח ש-$latex w\in L_{q,p}^{k}$ היא מילה שמעבירה את $latex q$ ל-$latex p$ ועוברת ב-$latex q_{k}$ בדיוק פעמיים. עכשיו אפשר לפרק את $latex w$ כך: $latex w=uzv$ כך ש-$latex v\in L_{q,q_{k}}^{k-1}$ ואילו $latex u\in L_{q_{k},p}^{k-1}$. ומה עם $latex z$? ובכן, הוא מייצג את החלק בריצה שבין ההגעה הראשונה ל-$latex q_{k}$ ובין ההגעה השניה ל-$latex q_{k}$, כלומר $latex z\in L_{q_{k},q_{k}}^{k-1}$.

ועכשיו בואו נניח ש-$latex w\in L_{q,p}^{k}$ היא מילה שמעבירה את $latex q$ ל-$latex p$ ועוברת ב-$latex q_{k}$ בדיוק שלוש פעמיים. עכשיו אפשר לפרק את $latex w$ בתור $latex w=uz_{1}z_{2}v$ כאשר $latex z_{1},z_{2}\in L_{q_{k},q_{k}}^{k-1}$.כבר הבנתם לאן אני חותר? אם לא, בואו נדבר על מילה שעוברת ב-$latex q_{k}$ בדיוק ארבע פעמים - עכשיו נפרק אותה בתור $latex uz_{1}z_{2}z_{3}v$ כאשר $latex z_{1},z_{2},z_{3}\in L_{q_{k},q_{k}}^{k-1}$. ובאופן כללי? באופן כללי זה מסורבל מדי לכתוב את כל ה-$latex z$-ים הללו, ולכן אפשר להשתמש בחזקה של שפה: אם $latex w\in L_{q,p}^{k}$ היא מילה שמעבירה את $latex q$ ל-$latex p$ ועוברת ב-$latex q_{k}$ בדיוק $latex t$ פעמים, אז אפשר לפרק אותה כך: $latex w=uzv$ כך ש-$latex z\in\left(L_{q_{k},q_{k}}^{k-1}\right)^{t-1}$. הפעם ה-$latex t-1$ שמופיע למעלה הוא לא אינדקס אלא כן בא על תקן חזקה של שפה.

מה המסקנה? כדי לתאר את כל המילים ב-$latex w\in L_{q,p}^{k}\backslash L_{q,p}^{k-1}$ אנחנו רוצים לתאר את כל המילים שהן שרשור של מילה אחת מתוך $latex L_{q,q_{k}}^{k-1}$, מילה אחת מתוך $latex L_{q_{k},p}^{k-1}$, וביניהן מילה אחת מתוך אחת מהחזקות האפשריות של $latex L_{q_{k},q_{k}}^{k-1}$ - כל חזקה אפשרית. האם אנחנו מכירים פעולה שנותנת לנו את זה? בוודאי - זו בדיוק הפעולה של סגור-קלייני! אמרתי לכם שנבין סוף סוף למה בדיוק צריך את הפעולה הזו? הנה, זו הנקודה המדוייקת שבה היא צצה מעצמה.

נסכם. קיבלנו את המשוואה $latex L_{q,p}^{k}=L_{q,p}^{k-1}\cup L_{q,q_{k}}^{k-1}\left(L_{q_{k},q_{k}}^{k-1}\right)^{*}L_{q_{k},p}^{k-1}$, והמשוואה הזו מסיימת את ההוכחה, כי היא מתארת את היצירה של $latex L_{q,p}^{k}$ מתוך שפות שאנחנו כבר יודעים ששייכות לקבוצה האינדוקטיבית שלנו, בעזרת פעולות הסגור שלנו (איחוד, שרשור וסגור-קלייני). בדרך כלל אני לא נוהג להתלהב ממשוואות כי זו לא הפואנטה במתמטיקה, אבל את המשוואה הזו אני אוהב בגלל הסיפור הציורי שהיא מספרת (כל הקטע הזה של “עובר ב-$latex q_{k}$ בדיוק כך-וכך פעמים”). אני מקווה שאתם מסכימים.


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com