על משחקים ומספרים (חלק ב': מספרים. וקצת משחקים)

בפוסט הקודם התחלתי לבנות קבוצה של מספרים שהמוטיבציה אליהם הגיעה איכשהו מתוך משחקים קומבינטוריים. כזכור, הבניה הייתה פשוטה להפליא: כל מספר מיוצג על ידי אובייקט מהצורה \(\left\{ L|R\right\} \) כאשר \(L,R\) הן קבוצות, וכלל הבניה שלנו הוא ש"מספר" הוא אובייקט … להמשיך לקרוא

על משחקים ומספרים (חלק א': משחקים. וקצת מספרים)

בראשית ימי הבלוג, חלק מהפוסטים הראשונים שפרסמתי עסקו או בתורת המשחקים, או בבנייה השיטתית של מערכות המספרים המרכזיות במתמטיקה (הטבעיים, השלמים, הרציונליים, הממשיים והמרוכבים). אני רוצה עכשיו לחזור לנושאים הללו באופן שאיכשהו מצליח לחבר את שניהם, בהתבסס על שני ספרים … להמשיך לקרוא

משפט קלייני – הוכחה נוספת

אולי המשפט המרכזי בסדרת הפוסטים שלי על שפות רגולריות היה משפט קלייני. כזכור, שפה רגולרית היא שפה שקיים אוטומט סופי דטרמיניסטי שמקבל אותה, אבל משפט קלייני נתן אפיון שונה לגמרי עבורה, שאפשר לנו להבין מה המבנה הכללי של אוסף השפות … להמשיך לקרוא

למת הניפוח לשפות רגולריות – גרסה מלאה

הצגתי כאן בעבר את למת הניפוח לשפות רגולריות, ואני רוצה לחזור עכשיו לנושא ולהציג גרסה נוספת, מוכללת, של הלמה – גרסה שהיא חזקה מספיק כדי לתת לנו תוצאת "אם ורק אם". כזכור, למת הניפוח נתנה לנו תנאי הכרחי לכך ששפה … להמשיך לקרוא

משפט מייהיל-נרוד – נקודת מבט נוספת, ואלגוריתמי מינימיזציה

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

בעיות הכרעה עבור שפות פורמליות

כל מה שעשיתי עד כה בפוסטים על שפות פורמליות היה, במובן מסויים, "בתוך" המודלים שהצגתי – זה של אוטומט סופי עבור שפות רגולריות, וזה של דקדוקים חסרי הקשר ואוטומטי מחסנית עבור שפות חסרות הקשר. כל הדברים שעשיתי נעשו בעזרת המודלים … להמשיך לקרוא

שפות חסרות הקשר – תכונות סגור

הפוסט הקודם שלי על שפות חסרות הקשר היה כבד יחסית, אז בואו נישאר הפעם במסגרת הדברים הקלילים. אני ממשיך עם ההקבלה שלנו לשפות רגולריות, והגענו לשלב שבו אנחנו מוכיחים כל מני תכונות סגור שונות ומשונות – פעולות שאפשר להפעיל על … להמשיך לקרוא

חידת יום הולדת

עושה רושם שבימים האחרונים הרשת עוסקת בהתלהבות בחידה קטנה וחביבה. מבחינה מתמטית היא לא מתוחכמת יותר מדי, ולא שונה מהותית באופיה מחידת ה"עיניים כחולות" שכבר דיברתי עליה בבלוג, אבל העובדה שהיא זוכה לפופולריות שכזו מעידה על כך שמשהו בניסוח שלה … להמשיך לקרוא

שפות חסרות הקשר – למת הניפוח, הלמה של אוגדן ושפות רב משמעיות

אני ממשיך לדבר על תכונות שונות ומשונות של שפות חסרות הקשר, וממשיך עם האנלוגיה לשפות רגולריות. אחד מהדברים שעשינו בשפות רגולריות היה להוכיח משהו שנקרא "למת הניפוח", שהצביע על סוג של תבניתיות שכל שפה רגולרית חייבת לקיים. משהו מאוד דומה … להמשיך לקרוא

שקילות אוטומט מחסנית ודקדוק חסר הקשר

בפוסט הקודם הצגתי את המודל של אוטומט מחסנית. המטרה הייתה להציג מודל של אוטומט שמחלקת השפות שמתאימה לו היא בדיוק מחלקת השפות חסרות ההקשר. לצורך זה, חשבתי על אלגוריתם פשוט לזיהוי שפה של דקדוק חסר הקשר כלשהו, ואז לקחתי מודל … להמשיך לקרוא

אוטומט מחסנית

בפוסטים הקודמים על שפות פורמליות הגדרתי את המושג של שפה חסרת הקשר. שפה היא חסרת הקשר אם יוצר אותה דקדוק חסר הקשר. זה מייצג גישה שונה לשפות פורמליות ביחס לזו שבה נקטתי עבור שפות רגולריות – שם הגדרתי את המחלקה … להמשיך לקרוא

אז מה הקשר בין דקדוקים חסרי הקשר ופונקציות יוצרות?

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך \(n\) הוא מסלול ב-\(\mathbb{Z}^{2}\) שמתחיל ב-\(\left(0,0\right)\) ומסתיים ב-\(\left(n,0\right)\) ומורכב משלושה סוגים אפשריים של צעדים: ימינה, למעלה-ימינה ולמטה-ימינה. כלומר, אנחנו כרגע ב-\(\left(x,y\right)\) אז אנחנו יכולים לעבור אל \(\left(x+1,y+\delta\right)\) כאשר \(\delta\in\left\{ -1,0,1\right\} \). והנה העלילה … להמשיך לקרוא

מבוא לדקדוקים חסרי הקשר

הפוסט על משפט נרוד מהווה לטעמי סיום הולם לנושא של שפות רגולריות, אבל מהנושא הזה יש קפיצה טבעית מאוד אל נושא קרוב ברוחו – שפות חסרות הקשר. בזמן שהכלי העיקרי שבו השתמשנו כדי לתאר שפות רגולריות היה אוטומטים, עבור שפות … להמשיך לקרוא

משפט מייהיל-נרוד

עבורי, משפט מייהיל-נרוד הוא המשפט האולטימטיבי בכל הנוגע להבנה של מה בעצם הופך שפה לרגולרית או ללא רגולרית, איך "אמור" להיראות אוטומט עבורה, ובכלל איך עובד הקטע הזה של אוטומטים. לטעמי זה המשפט היפה ביותר בחומר הזה. אבל אני לא … להמשיך לקרוא

למת הניפוח לשפות רגולריות

עד עכשיו בסדרת הפוסטים שלי על שפות רגולריות נראה לי שהצלחנו לקבל מושג לא רע לגבי מה הן: ראינו מצד אחד אפיון שלהן בתור שפות שניתנות לזיהוי על ידי מספר מודלי חישוב (אוטומטים), ומצד שני אפיון שלהן בתור קבוצה אינדוקטיבית … להמשיך לקרוא

ביטויים רגולריים

בפוסט האחרון שלנו על שפות רגולריות הוכחתי שניתן לבנות שפה רגולרית מתוך שפות פשוטות מאוד (סינגלטונים שמכילים מילה אחת מאורך 1 לכל היותר) ושלוש פעולות יצירה פשוטות – איחוד, שרשור וסגור-קלייני. ביטויים רגולריים הם שיטת ייצוג לשפות רגולריות שמשתמשת בדיוק … להמשיך לקרוא

פרדוקס המבחן האמריקאי

נתקלתי בדף הפייסבוק של מכון דוידסון בחידה הזו, שכבר ראיתי אינספור גלגולים שלה ברחבי האינטרנט: החידה מוצגת לפעמים בתור "פרדוקס" למרות שאני חושב שהיא אינה כזו; השם "פרדוקס המבחן האמריקאי" הוא המצאה שלי כדי שתהיה לפוסט כותרת מעניינת. ובכן, מה … להמשיך לקרוא

מיקסומיה – תורת הטבע השלמה

בשבועות האחרונים היה קשה להתעלם מפרסומת פייסבוק שחלחלה לה אט אט אל המעגלים שלי. בואו ניתן לה לדבר בעד עצמה: מי שילחץ על הלינק יגיע לאתר שכותרתו "מיקסומיה – תורת הטבע השלמה" ויש בו כל מני… דברים. הרושם המיידי שהתקבל … להמשיך לקרוא

שפות רגולריות – משפט קלייני

את הדיון שלי על שפות רגולריות התחלתי בהצגה של מושג האוטומט הסופי הדטרמיניסטי. האוטומט הזה היה מין מכונת חישוב תאורטית שמבצעת פעולה של זיהוי מתי מילה שייכת או לא שייכת לשפה כלשהי. הגדרתי את אוסף השפות הרגולריות בתור השפות שמתקבלות … להמשיך לקרוא

שפות רגולריות – תכונות סגור (חלק ב')

בפוסט הקודם דיברתי על תכונות סגור יחסית סטנדרטיות של שפות רגולריות (עם החריג של פעולת סגור קלייני, שהייתי צריך לתת לה מוטיבציה מורכבת כלשהי). עכשיו בואו נעבור לתכונת סגור שונה לגמרי – הומומורפיזם. המילה הזו בטח מוכרת לכל מי שעשה … להמשיך לקרוא