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