אוטומטים ושפות פורמליות – אוניברסיטת אריאל
אוטומטים ושפות פורמליות
דרישות קדם
מבנים דיסקרטיים למדעי המחשב בציון 60 וגם תורת המספרים האלגוריתמית בציון 60 וגם לוגיקה ותורת הקבוצות בציון 60
מטרת הקורס
זהו הקורס הראשון מבין שני קורסים שמטרתם הכרה עם מודלים חישוביים שימושיים (בעלי כח חישובי הולך ועולה).
זהו קורס תיאורטי-מתמטי באופיו, עם דגש חזק על הוכחת המסקנות השונות לגבי ומודלים והשפות (הפורמליות) הנתפשות על ידו. קורס זה יעסוק בעיקר בכוחם של אוטומטים סופיים וכן אוטומט מחסנית אי דטרמיניסטי, התופסים את השפות הרגולריות והשפות חסרות ההקשר בהתאמה.
מבנה הציון בקורס
בקורס יינתנו 3-5 תרגילי בית שמשקלם הכולל %20 חובה. התרגילים ייבדקו סלקטיבית, ויפורסם פתרון של כל תרגיל.
ציון הקורס יורכב מ-%80 מבחן + %20 מטלות.
ציון המטלות ישוקלל רק לעוברים את הבחינה הסופית בציון 60 לפחות.
הרצאות
הסדר הבא הינו משוער, ונתון לשינויים ללא הודעה מראש.
חלק – 1 אוטומטים סופיים ושפות רגולריות
- הרצאה 1. מבוא לקורס. דיון לא פורמלי במושג המודל החישובי ומגבלות הכח של מודלים "סבירים." סקירה של מודלים שנתעניין בהם בקורס עם דגש על מודלים שתופסים את השפות הרגולריות.
הגדרות בסיסיות (א"ב, מילים, שפה פורמלית, פעולות על שפות). הגדרה פורמלית של אוטומט סופי דטרמיניסטי ודוגמות.
- הרצאה 2. הגדרה פורמאלית של רגולריות של שפה. דוגמאות לשפות רגולריות. הוכחת טענות על שפות והוכחת נכונות בניה של אוטומט. דוגמה לשפה לא רגולרית (שובך היונים). תכונות סגור של שפות רגולריות.
- הרצאה 3. הגדרת אוטומט אי-דטרמיניסטי ללא מסעי אפסילון, ודיון במוטיבציה לאי דטרמיניזם, באמצעות דוגמאות. הוכחת שקילות בין שני המודלים DFA, NFA.
- הרצאה 4. הגדרת אוטומט אי-דטרמיניסטי עם מסעי אפסילון, דוגמות, הוכחת שקילות בין 𝐴𝐹𝑁 − 𝜖 לבין 𝐴𝐹𝑁 (ומכאן גם ל FAD). הגדרת ביטויים רגולריים. הוכחת שקילות ל-DFA. תכונות סגור, ותכונות סגור בעזרת 𝑁𝐹𝐴 − 𝜖.
- הרצאה 5. למת הניפוח לשפות רגולריות. דוגמות לשימוש בלמה.
- הרצאה 6. בעיות הכרעה ל-DFA. התחלת אפיון אלגברי של שפות רגולריות.
- הרצאה 7. המשך אפיון אלגברי של השפות הרוגלויות – משפט נרוד, הוכחה ושימושים. אלגוריתם לצמצום אס"ד, הוכחה.
חלק – 2 דקדוקים, עם דגש על דח"ה
- הרצאה 8. מבוא לדקדוקים (ככלי לביטוי שפות, לאו דווקא חסרי הקשר). ההיררכיה של חומסיקי. דקדוקים רגולריים (לינארי ימני\שמאלי, עם הוכחת שקילות ל-(DFA)).
- הרצאה 9. דקדוקים חסרי הקשר (CFG -) המשך. הגדרת שפות ח"ה. דוגמאות ותכונות סגור בסיסיות שלהן. עצי גזירה של CFG, גזירות קנוניות, רב משמעיות של דקדוקי CFG.
- הרצאה 10. פישוט של CFG. צורות נורמליות של CFG. למת הניפוח לשפות חסרות הקשר.
- הרצאה 11. אוטומט מחסנית א"ד. דיון בנחיצות של אי-דטרמיניזם באוטומט מחסנית. קבלה ע"י ריקון וע"י מצב מקבל, ושקילות בין שני המודלים.
- הרצאה 12. אוטומט מחסנית – המשך. הוכחת שקילות ל-CFG. תכונות סגור של שפות חסרות הקשר.
- הרצאה 13. בעיות הכרעה בסיסיות. חזרה כללית והצגת הנחיות לקראת המבחן.
ביבליוגרפיה
ספר הקורס: אוטומטים ושפות פורמליות בהוצאת האוניברסיטה הפתוחה. 1991 CGF CGF כרכים א,ב (עבור חלקים 1,2 בהתאמה).
ההרצאות שלנו יעקבו באופן צמוד אחרי (חלקים גדולים מ) ההרצאות של הטכניון.