הרצאה 1 - 7.3.12

• פרטים טכניים.
• מבוא: סקירה של הנושאים בקורס, דוגמאות לבעיות מכל נושא (בעיית העצירה, וכו'), קצת סיבוכיות, גרפים, שיטות הוכחה.
• אוטומט סופי דטרמיניסטי (DFA):
  • הגדרה לא פורמלית (עיגולים וחצים).
  • שפות ואלפבית.
  • הגדרה פורמלית של DFA.
  • איך מוכיחים מה השפה שהאוטומט מקבל.
  • שפות רגולריות.
  • פעולות על שפות רגולריות: הוכחות של סגירות תחת איחוד ושרשור.

תרגול 1 - 9.3.12

• פורים שמח!!

הרצאה 2 - 14.3.12

קישור למצגת:
מצגת 2

הרצאה 3 - 21.3.12

• למת הניפוח (pumping lemma) - דרך להוכיח ששפה היא לא רגולרית.
• הגדרת יחס שקילות מעל שפות, ויחס דומה מעל אוטומטים, הקשר בין מחלקות השקילות של שני היחסים.
  • משפט Myhill-Nerode, ששפה היא רגולרית אם"ם יחס השקילות מחלק אותה למספר סופי של מחלקות שקילות. הוכחת המשפט, ויישומים.
• מציאת אוטומט מינימלי.
• עוד פעולות ששומרות על סגירות: חיתוך וחלוקה של שפות.
• ההומומורפיזם שמחליף בין אותיות בודדות ומילים.

קישור למצגת:
מצגת 3

תרגול 3 - 22.3.12

• הוכחת סגירות פעולות על שפות רגולריות
  • הוכחת סגירות על Reverse (רעיון ההוכחה הוא להוסיף מצב מקבל, ולהפוך את כל החצים)
  • הוכחת סגירות על Dropchar(L) (משכפלים את האוטומט, ומוסיפים חצי אפסילון מכל מצב למצב הבא באוטומט השני)
  • הפעולה: כל המחרוזות x כך שקיימת מחרוזת y באורך זהה כך ש xy שייך ל L. בהוכחה יוצרים שלשות של מצבים, ומנחשים באיזה מצב המילה x מסתיימת.