PDA

צפה בגרסה המלאה : למת הניפוח



דויד
19-11-2020, 14:08
אשמח לעזרה עם השאלה

Yes
20-11-2020, 13:35
רמז: אתה יכול להסתכל על מילים שיש בהן רק $a$-ים.

דויד
20-11-2020, 13:39
איך אנחנו מתייחסים לb?

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

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

Yes
20-11-2020, 23:36
אתה צודק. פספסתי את זה. בכל אופן, הנה הצעת פתרון.

נניח בשלילה שהשפה כן רגולרית, ולכן מקיימת את למת הניפוח עבור $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$.

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

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

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

דויד
21-11-2020, 13:54
הבנתי, תודה רבה