מציג תוצאות 1 עד 9 מתוך 9

אשכול: למת הניפוח

  1. #1
    הסמל האישי שלדויד משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל למת הניפוח

    אשמח לעזרה עם השאלה
    קבצים מצורפים קבצים מצורפים

  2. #2
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

  3. #3
    הסמל האישי שלדויד משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל

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

  4. #4
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

  5. #5
    הסמל האישי שלדויד משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל

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

  6. #6
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

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

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

  7. #7
    הסמל האישי שלדויד משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל

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

  8. #8
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

  9. #9
    הסמל האישי שלדויד משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל

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

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 8

הרשאות

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

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו