על הבעיה הקשה של מלכות השחמט והבעיה הקשה עוד יותר של מלקות התקשורת

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

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

לפני חודש וקצת הצליחה תוצאה מתמטית נחמדה להיכנס אל החדשות לא בשל הסיבות שבגללן היא טובה, אלא בעיקר אלו שבגללן היא בעייתית: ההוכחה שלה היא (לכאורה) בגודל מפלצתי של 200 טרה-בייט. כמה זה הרבה? נאמר, זה פי 40 יותר מידע מאשר היה בשרתי ויקיפדיה ב-2010, ויש עוד שלל המחשות. בקיצור, זה הרבה מאוד. הנתון הזה …

משפט קוק-לוין

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

בפוסט הקודם דיברתי על תכונות סגור יחסית סטנדרטיות של שפות רגולריות (עם החריג של פעולת סגור קלייני, שהייתי צריך לתת לה מוטיבציה מורכבת כלשהי). עכשיו בואו נעבור לתכונת סגור שונה לגמרי – הומומורפיזם. המילה הזו בטח מוכרת לכל מי שעשה קורס באלגברה מופשטת, וספציפית בתורת החבורות. הומומורפיזם בין שתי חבורות הוא פונקציה $latex h:G\to H$ …

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

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

אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

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