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

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

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

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

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

תכירו – מסלולי מוצקין. מסלול מוצקין מאורך \(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 לכל היותר) ושלוש פעולות יצירה פשוטות – איחוד, שרשור וסגור-קלייני. ביטויים רגולריים הם שיטת ייצוג לשפות רגולריות שמשתמשת בדיוק … להמשיך לקרוא

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

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

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

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

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

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

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

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

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

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

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

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

אוטומטים ושפות רגולריות – מבוא

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

בעיית המטבעות

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

חישוב קוונטי – דברי סיום ופרידה

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

חישוב קוונטי – האלגוריתם של שור

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

חישוב קוונטי – האלגוריתם של סימון

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

שערים ומעגלים קוונטיים – מבוא על קצה המזלג

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

אלגוריתם גרובר

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