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

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

כמובן, חיש קל עולה מאליה השאלה - אילו שפות הן רגולריות? קל לראות שהשפה הריקה \( \emptyset \) היא רגולרית - אוטומט עם מצב יחיד שאינו מקבל. קל גם לראות שאוסף כל המילים מעל \( \Sigma \), שאותו סימנתי בסימון \( \Sigma^{*} \), הוא רגולרי - אוטומט עם מצב יחיד שהוא מקבל וכל אות מובילה ממנו לעצמו. טיפה יותר מעניין לבנות אוטומט שמקבל בדיוק מילה אחת - לכל מילה \( w=\sigma_{1}\dots\sigma_{n} \) האוטומט הזה יכלול \( n+1 \) מצבים שהאוטומט עובר בהם לפי הסדר כל עוד הוא קורא אותיות שמתאימות למילה \( w \), ואם מתישהו משהו השתבש או שהוא קיבל יותר מ-\( n \) אותיות, הוא עובר למצב “בור” שאינו מקבל וכל קשת ממנו נכנסת חזרה אליו. נסו בעצמכם לצייר אוטומט כזה עבור מילים ספציפיות ולכתוב אותו פורמלית. זה קל.

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

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

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

עוד פעולת סגור קלילה היא משלים - קחו רגע כדי לשכנע את עצמכם שהאוטומט עבור משלים של שפה (המשלים של \( L \), שאסמן \( \overline{L} \), הוא כל המילים ב-\( \Sigma^{*} \) שאינן ב-\( L \)) הוא פשוט האוטומט של השפה, בהיפוך של המצבים המקבלים (מי שהיה מקבל הופך ללא-מקבל, ומי שקודם לא היה מקבל הופך למקבל); אבל, רק בתנאי שהאוטומט הזה הוא אוטומט סופי דטרמיניסטי.

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

כעת, הראינו סגירות לאיחוד וחיתוך רק עבור זוגות של שפות, אבל באינדוקציה קל להראות שיש סגירות לחיתוך ואיחוד של כל מספר סופי של שפות. מכאן אנחנו מקבלים מייד את הטענה על כך שכל שפה סופית היא רגולרית - היא איחוד של מספר סופי של סינגלטונים, וראינו שסינגלטון הוא שפה רגולרית. עם זאת, הדרישה על הסופיות כאן היא קריטית - אפשר לבנות את השפה \( \left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) בתור איחוד אינסופי של סינגלטונים, וכבר ראינו שזו לא שפה רגולרית. אם כן, אין לנו סגירות לאיחוד אינסופי. מכך נובע גם שאין סגירות לחיתוך אינסופי, שכן אפשר להציג איחוד באמצעות חיתוך ומשלים - זה מה שמכונה “כלל דה-מורגן” (אחד משניהם, יש שניים שדואליים זה לזה): \( \bigcup L_{n}=\overline{\bigcap\overline{L_{n}}} \). אם חיתוך אינסופי היה פעולת סגור, אז מכיוון שבאגף ימין מתרחשות רק פעולות סגור, היינו מקבלים שגם אגף שמאל הוא תכונת סגור, וכרגע הסברתי למה הוא לא.

עד עכשיו השתעשענו עם תכונות סגור שהן פעולות “רגילות” על קבוצות. אבל שפה היא לא סתם קבוצה - היא קבוצה של מילים, ועל מילים אפשר לעשות פעולות מגניבות שלא דיברתי עליהן עד עכשיו. הפעולה הבסיסית שאפשר לבצע על מילים היא לשרשר שתי מילים - לחבר אותן זו לזו כדי ליצור מילה חדשה. אם \( u=\sigma_{1}\dots\sigma_{n} \) ו-\( v=\tau_{1}\dots\tau_{k} \) הן שתי מילים כלשהן, אז השרשור שלהן הוא \( u\cdot v=\sigma_{1}\dots\sigma_{n}\tau_{1}\dots\tau_{k} \). לרוב אני אשמיט את הנקודה, כפי שעושים לעתים קרובות עם סימונים דמויי כפל שכאלו.

השימוש הזה ב”מילים” וב”כפל” עשוי להישמע מוכר לחלק מהקוראים - זו טרמינולוגיה שנפוצה גם בתורת החבורות. ואכן, לרגע נראה ש-\( \Sigma^{*} \) היא חבורה ביחס לפעולת השרשור הזו. זו פעולה בינארית, אסוציאטיבית, ואפילו עם איבר יחידה נייטרלי (המילה הריקה \( \varepsilon \), כמובן). רק מה, אין לנו “הופכי”. אם \( u \) היא מילה לא ריקה, אז לא קיימת מילה \( v \) כך ש-\( uv=\varepsilon \). זה כאילו ש-\( \Sigma^{*} \) היא המספרים השלמים, בלי האפשרות לכפול בהופכי של מספר (“לחלק”). עדיין, גם מבנה אלגברי שהוא כמעט-כמו-חבורה-רק-בלי-הופכי הוא מעניין ונקרא מונואיד. לא חייבים להיות בקיאים במונואידים כדי להבין את מה שאעשה בהמשך, אבל נחמד לדעת שהמושג קיים.

כעת, שרשור היא פעולה על מילים, לא על שפות, אבל נובעת ממנה די בקלות פעולה על שפות: \( L_{1}\cdot L_{2}=\left\{ uv\ |\ u\in L_{1},v\in L_{2}\right\} \). דהיינו, לוקחים את כל הזוגות של מילה מפה ומילה משם, ומשרשרים. תשוו את זה עם הגדרה סטנדרטית מאלגברה לינארית וכדומה - \( V+U=\left\{ v+u\ |\ v\in V,u\in U\right\} \).

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

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

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

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

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

בואו ננסה להבין רגע מה קורה בשפה הרגולרית הטיפוסית. את השפות הסופיות הבנו, אז בואו ניקח שפה רגולרית אינסופית. יש אוטומט סופי דטרמיניסטי \( A \) שמקבל אותה. ננקוט בתעלול דומה לזה שבו השתמשתי כדי להוכיח ש-\( \left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) אינה רגולרית: נסמן ב-\( n \) את מספר המצבים של \( A \), ועכשיו נשאל את עצמנו איך \( A \) רץ על מילה \( z \) שאורכה הוא לפחות \( n \). מכיוון שעל מילה באורך לפחות \( n \) האוטומט \( A \) יראה בריצה שלו לפחות \( n+1 \) מצבים, יהיה מצב \( q \) שבו הוא מבקר פעמיים. לכן אפשר לפרק את \( z \) לשלושה חלקים: \( z=uvw \), כאשר \( u \) הוא המילה שנקראת עד שמגיעים ל-\( q \); \( v \) הוא המילה שנקראת כשהולכים מ-\( q \) אל עצמו, ו-\( w \) היא המילה שנקראת מ-\( q \) בדרך אל מצב מקבל כלשהו.

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

די ברור שאנחנו צריכים קיצור כלשהו כאן - במקום לכתוב \( vvvvv \) יותר הגיוני לכתוב \( v^{4} \). נוח גם להגדיר \( v^{0}=\varepsilon \), ואז את הטענה שלי למעלה ניתן לסכם כך: \( uv^{k}w \) שייכת לשפה לכל \( k\ge0 \).

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

ובכן, לא. וכדי לראות את זה, בואו ניקח שפה מעל \( \Sigma=\left\{ a,b\right\} \) שכוללת את כל המילים מאורך זוגי. האם אפשר לבנות אותה על ידי אברי הבסיס והפעולות שלנו?

אפשר להתחיל מהשפה \( \left\{ a\right\} \), לשרשר אותה לעצמה ולקבל את השפה \( \left\{ aa\right\} \), לאחד עם \( \left\{ bb\right\} \) שנבנית באופן דומה ועם \( \left\{ \varepsilon\right\} \) ולקבל \( \left\{ aa,bb,\varepsilon\right\} \). זו התחלה טובה, אבל זה עדיין לא מכסה את כל המילים מאורך 2 שאמורות להיות בשפה - עם עוד קצת עבודה אפשר לקבל את \( \left\{ aa,bb,ab,ba,\varepsilon\right\} \), וזה אכן מכסה לנו את כל המילים עד וכולל אורך 2. עכשיו, אם אני אפעיל על השפה הזו את הפעולה “החזר את השפה שכוללת את כל החזקות של המילים בשפת הקלט”, אני אקבל שפה נאה למדי - היא תהיה אינסופית, ויהיה בה למשל את \( \left(aa\right)^{k} \) לכל \( k \), וגם מילים כמו \( abababab \). הבעיה היא שזה לא מספיק. מי חסר? למשל, המילה \( abba \). היא לא מתקבלת בתור חזקה של אף אחת מהמילים \( aa,bb,ab,ba \).

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

זה מוביל אותנו להגדרת חזקה של שפה, שמוגדרת באופן המתבקש: \( L^{0}=\left\{ \varepsilon\right\} \) ו-\( L^{k}=L\cdot L^{k-1} \). כלומר, החזקה ה-\( k \) של \( L \) היא כל המילים שמתקבלות משרשור של \( k \) מילים מתוך \( L \). עכשיו, הפעולה שאני מעוניין בה היא כזו שלוקחת את כל החזקות של השפה “בבת אחת”:

\( L^{*}=\bigcup_{k=0}^{\infty}L^{k} \)

הפעולה הזאת נקראת “איטרציה” או “סגור קלייני” או “כוכב קלייני” וכדומה. אני קורא לה לרוב סגור קלייני. זו הפעולה שחיפשנו: הטענה שלי היא שאפשר לבנות את כל השפות הרגולריות מתוך \( \emptyset,\left\{ \varepsilon\right\} \), כל הסינגלטונים של אותיות ב-\( \Sigma \) ופעולות האיחוד, השרשור וסגור קלייני. זו טענה כבדה שדורשת הוכחה, וההוכחה היא מבריקה ויפהפיה ולא קלה בכלל, ולכן אחכה איתה להמשך.

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

בואו נחשוב על איך יתנהג אוטומט שמקבל את \( L^{*} \). הוא מן הסתם יהיה מבוסס על אוטומט \( A \) שמקבל את \( L \), ויהיה בו רעיון דומה לזה שהיה באוטומט עבור שרשור שפות: מסמלצים את \( A \) ובכל פעם שבה מגיעים למצב מקבל, אפשר “לנחש” שסיימנו לקרוא מילה אחת וצריך להתחיל את ריצת \( A \) מהתחלה - כלומר, לבצע מסע-\( \varepsilon \) למצב ההתחלתי של \( A \). זה כמעט עובד, למעט נקודה מעצבנת אחת: שימו לב לכך ש-\( \varepsilon\in L^{*} \) תמיד, מכיוון ש-\( L^{0}=\left\{ \varepsilon\right\} \) נכלל באיחוד. בפתרון שהצעתי זה עתה, אם המצב ההתחלתי של \( A \) הוא לא מקבל, אז \( \varepsilon \) לא תתקבל (למה?).

אפשר כמובן להגיד - אוקיי, אז בואו נעשה מעבר-\( \varepsilon \) מהמצב ההתחלתי של \( A \) למצב מקבל שאי אפשר לצאת ממנו. כלומר, בתחילת הריצה שלו האוטומט יחליט אם בא לו להמר שהקלט שלו ריק ולקבל אותו ישר, או להתחיל חישוב ישיר. אבל גם זה ייכשל. למה? כי במהלך הריצה שלו \( A \) עשוי להגיע חזרה אל המצב ההתחלתי באופן תמים תוך כדי קריאת מילה למרות שאותה מילה לא בשפה (ולא על ידי הגעה למצב מקבל ואז מעבר-\( \varepsilon \) למצב ההתחלתי). בעצם, אין הבדל בין הפתרון שהצעתי כרגע ובין להפוך את \( q_{0} \) למצב מקבל.

אז מה עושים? אפשר, כמובן, לומר שזה לא באמת חשוב - שמספיק להוכיח ש-\( \bigcup_{k=1}^{\infty}L^{k} \) רגולרית כי אחר כך אפשר לאחד אותה עם \( \left\{ \varepsilon\right\} \) הרגולרית. אבל זה תרגיל סביר בבניית אוטומטים לבנות אוטומט שיודע לקבל את \( L^{*} \) ישירות. הפתרון טיפה מסורבל אבל לא כזה נורא כשברור מה הוא בא להשיג. אנחנו פשוט מוסיפים מצב התחלתי חדש ומצב מקבל חדש (ומבטלים את שאר המצבים המקבלים). מהמצב ההתחלתי אפשר לעבור במסע-\( \varepsilon \) ישירות למצב המקבל, או למצב ההתחלתי של \( A \); ומכל מצב מקבל של \( A \) אפשר לעבור למצב המקבל “האמיתי” או לחזור למצב ההתחלתי של \( A \), שוב באמצעות מסע-\( \varepsilon \). נסו לצייר את זה לעצמכם ולהשתכנע שזה יעבוד.

בפוסט הבא - עוד תכונות סגור! אפילו יותר מופרעות!