למת הניפוח

למת הניפוח

Tammy Dagan (guest) 24 Jun 2010 07:28

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

Re: למת הניפוח

benny_chor 24 Jun 2010 07:58

You are right. When proving [$$ \{0^n1^n\}$$] is not regular, we chose not to use that condition
($|xy| \leq k$) and demonstrate the proof can still be completed.

If you do use it, the proof indeed becomes a bit easier (not that it was that hard in the first place).