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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\( 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\} \)

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

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

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

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

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

\( 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\} \)

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

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

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

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

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

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

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

נסכם. קיבלנו את המשוואה \( 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} \), והמשוואה הזו מסיימת את ההוכחה, כי היא מתארת את היצירה של \( L_{q,p}^{k} \) מתוך שפות שאנחנו כבר יודעים ששייכות לקבוצה האינדוקטיבית שלנו, בעזרת פעולות הסגור שלנו (איחוד, שרשור וסגור-קלייני). בדרך כלל אני לא נוהג להתלהב ממשוואות כי זו לא הפואנטה במתמטיקה, אבל את המשוואה הזו אני אוהב בגלל הסיפור הציורי שהיא מספרת (כל הקטע הזה של “עובר ב-\( q_{k} \) בדיוק כך-וכך פעמים”). אני מקווה שאתם מסכימים.