בשיעור זה נלמד לקרוא הגדרות של שפות: נבחין בין סימן, מילה וקבוצת מילים, נבדוק שייכות ונמצא את כל המילים הקצרות ביותר. זהו הבסיס לתכנון אוטומטים בהמשך הקורס.
מה נלמד?
נבחין בין סימן, מילה ושפה; נקרא הגדרות עם חזקות ותנאים; ונמצא מילים קצרות בלי לנחש. ידע קודם: קבוצות, אי־שוויונות ושארית בחלוקה. אין צורך בידע על אוטומטים.
אבני הבניין
אלפבית \(\Sigma\) הוא קבוצה סופית של סימנים. מעל \(\Sigma=\{0,1,2\}\), המילה 1021 היא רצף של ארבעה סימנים. אין חשיבות לערכה כמספר. שפה היא קבוצה של מילים מעל אלפבית נתון.
| סימון | משמעות | דוגמה |
|---|---|---|
| \(\varepsilon\) | המילה הריקה, שאורכה אפס | אינה הסימן 0 |
| \(\Sigma^*\) | כל המילים הסופיות מעל האלפבית, כולל הריקה | ε, 0, 12, 222 |
| \(\varnothing\) | שפה שאין בה אף מילה | גודלה אפס |
| \(\{\varepsilon\}\) | שפה שיש בה מילה אחת | גודלה אחד |
| \(\lvert w\rvert\) | אורך המילה | \(\lvert abba\rvert=4\) |
| \(\#_a(w)\) | מספר הופעות הסימן במילה | \(\#_a(abba)=2\) |
שרשור מצמיד מילים: אם \(u=ab\) ו־\(v=ba\), אז \(uv=abba\). בדרך כלל \(uv\ne vu\). חזקה חוזרת על מילה: \((ab)^3=ababab\), ואילו \(a^3b^3=aaabbb\). לכל מילה \(u\), מתקיים \(u^0=\varepsilon\) וגם \(u\varepsilon=\varepsilon u=u\).
בקורס אין מעברי אפסילון באוטומטים. אין בכך איסור על המילה הריקה! אם שפה מכילה אותה, נצטרך שהמודל יקבל גם קלט באורך אפס. בהמשך נעשה זאת באמצעות מצב התחלתי מקבל.
דוגמה פתורה 1 — אורך נכון אינו מספיק
במטלה 1, שאלה 3, נתונה השפה:
\[L=\{a^n b^m\mid n,m\ge0,\ (n+m)\bmod3=1\}.\]קוראים את ההגדרה בשתי שכבות: תחילה כל ה־a ורק אחריהן כל ה־b; בנוסף, האורך משאיר שארית 1 בחלוקה ב־3. כל משתנה רשאי להיות אפס.
| מילה | צורה \(a^n b^m\)? | בדיקת האורך | מסקנה |
|---|---|---|---|
aab |
כן | \(3\bmod3=0\) | לא בשפה |
aaabbbb |
כן | \(7\bmod3=1\) | בשפה |
| \(\varepsilon\) | כן | \(0\bmod3=0\) | לא בשפה |
baaa |
לא | \(4\bmod3=1\) | לא בשפה |
האורך המזערי הוא 1. כל המילים הקצרות ביותר הן a ו־b: הזוגות \((n,m)\) הם \((1,0)\) ו־\((0,1)\). הדרישה להציג את כולן אינה מסתפקת בדוגמה אחת.
דוגמה פתורה 2 — יחס בין כמויות
במטלה 4, שאלה 1:
\[K=\{a^n b^{3k+1}c^k\mid n>0,\ k>0\}.\]האורך הוא \(n+4k+1\). הוא גדל כשמגדילים אחד מהפרמטרים, ולכן המינימום מתקבל ב־\(n=k=1\): המילה abbbbc, באורך 6. כדי לבדוק aabbbbbbbc, אין צורך לספור בעיניים: יש שבעה b ו־c אחד, אך \(7\ne3\cdot1+1\), ולכן היא אינה בשפה. המילה abbbbbbbcc כן בשפה: שבעה b מול שני c.
שיטה חוזרת: כתבו את מספר הסימנים בכל בלוק; מצאו את הפרמטרים; בדקו גם את סדר הבלוקים וגם את כל האילוצים. כאשר אותו משתנה מופיע פעמיים, אין לבחור לו שני ערכים שונים.
טעויות שכדאי לעצור בזמן
- \(\#_a(w)=\#_b(w)\) אינו אומר שכל ה־
aלפני כל ה־b; למשלabbaמקיימת את השוויון. - \(n\ge0\) מאפשר בלוק ריק; \(n>0\) אינו מאפשר זאת.
- “מכילה
10” דורש סימנים סמוכים. “מכילה1וגם0” הוא תנאי אחר.
תרגול
1. שלוש קבוצות
מעל \(\{a\}\), כמה מילים יש ב־\(\varnothing\), ב־\(\{\varepsilon\}\) וב־\(\Sigma^*\)? האם aaa שייכת לכל אחת?
רמז ופתרון
רמז: אל תבלבלו בין מספר המילים לאורך של מילה. פתרון: בהתאמה אפס, אחת, ואינסוף מילים. aaa שייכת רק ל־\(\Sigma^*\). כל מילה ב־\(\Sigma^*\) עדיין סופית באורכה.
2. כל המילים הקצרות
מצאו את כל המילים הקצרות בשפה \(\{a^{2n}b^m c^k\mid n,m\ge0,\ k>n+m\}\).
רמז ופתרון
רמז: גם \(n\) וגם \(m\) יכולים להתאפס. פתרון: בוחרים \(n=m=0,k=1\) ומקבלים רק c. המילה הריקה אינה מתאימה כי \(0>0\) שקרי. כל בחירה אחרת מגדילה את האורך.
3. אותה חזקה?
האם השפות \(A=\{(ab)^n\mid n\ge0\}\) ו־\(B=\{a^n b^n\mid n\ge0\}\) שוות? תנו מילה בכל אחד מההפרשים.
רמז ופתרון
רמז: בדקו \(n=2\). פתרון: abab ב־\(A\setminus B\), ואילו aabb ב־\(B\setminus A\). שתי השפות מכילות את ε ואת ab, אך הסכמה על חלק מהמילים אינה שוויון שפות.
מוכנים להתקדם כשאפשר להסביר מדוע מילה שייכת או אינה שייכת לשפה, ולציין בדיוק איזה תנאי נכשל.