למת הניפוח

[דויד]

אשמח לעזרה עם השאלה

[Yes]

רמז: אתה יכול להסתכל על מילים שיש בהן רק $a$-ים.

[דויד]

איך אנחנו מתייחסים לb?

[Yes]

המילים $a, aaa, aaaaaa$ למשל גם בשפה כי מותר $i=0$ עבור $b^i$. זה יכול לפשט קצת את ההוכחה בשלילה בעזרת למת הניפוח.

[דויד]

i לא אמור להיות גדול שווה ל4? זאת אומרת המילים מתחילות בלפחות 4 b..בעצם השפה לא מקבלת מילים שיש להן מספר a שהוא לא בסדרה למשל bbbbaa לא מתקבל כי אין סכום שנותן 2 בסיגמה. אני לא מוצא דרך למצוא מילה z שאיתה נבצע את ההוכחה עפי הלמה

[Yes]

אתה צודק. פספסתי את זה. בכל אופן, הנה הצעת פתרון.

נניח בשלילה שהשפה כן רגולרית, ולכן מקיימת את למת הניפוח עבור $n$ טבעי כלשהו. נסתכל כעת על המילה $b^4a^{\text{sig}(n)}$. האורך של המילה הזו גדול מ-$n$ ולכן מלמת הניפוח היא ניתנת לפירוק ל-$uvw$ בהתאם ללמה. כדי שהמילה הזו תהיה ניתנת לניפוח, לא יתכן ש-$v$ מכיל גם $a$ וגם $b$. לכן האופציות הן $v=b^i$ עבור $1\leq i \leq 4$ או $v=a^j$ עבור $1\leq j \leq n-4$.
במקרה הראשון, על פי הלמה, המילה $uv^0 w = b^{4-i}a^{\text{sig}(n)}$ בשפה. אבל זו סתירה כי $i\geq 1$.
במקרה שני, נסתכל על $uv^0 w = b^4 a^{\text{sig}(n)-j}$. על פי הלמה, המילה הזו בשפה. אבל זה לא ייתכן, שכן $\text{sig}(n)-j\neq \text{sig}(k)$ לכל $k$, כי זה ייתכן רק אם $j=n$, וראינו כי $j\leq n-4$.

מכאן שהשפה אינה רגולרית.

[דויד]

חושב שהבנתי את ההוכחה ונראה לי גם שהבנתי את ההסבר הקודם שלך. רצית להוכיח לפי למת הניפוח כי a^sigma לא רגולרית, אפשר להוכיח כי b^i רגולרית ומשרשרים אותם.
יכול להיות שזו עוד דרך?

[Yes]

לא. אמנם שפות רגולריות סגורות לשרשור, אבל אם אחת השפות לא רגולריות זה לא בהכרח אומר שהשרשור לא רגולרית. לדוגמה, אם ניקח $L_1 = \{ a^{\text{sig}(n)} \}$ ו-$L_2 = a^*$. אז $L_1 \circ L_2 = a a^*$ היא שפה רגולרית, למרות ש-$L_1$ לא רגולרית.

[דויד]

הבנתי, תודה רבה