אוטומטים ושפות פורמליות

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

סיכומי ההרצאות להלן מבוססים על קורס של פרופ' Amit Sahai, שלמעשה מבוסס על קורס ישן יותר של פרופ' Michael Sipser. מרבית הרעיונות מופיעים גם בספר של סיפסר "Introduction to the Theory of Computation".

תוכן עניינים

מבוא שפות פורמליות אוטומט סופי דטרמיניסטי אוטומט סופי לא דטרמיניסטי תכונות של שפות רגולריות סגירות תחת פעולות שונות למת הניפוח לשפות רגולריות משפט מיהיל-נרוד ביטויים רגולריים אוטומט מחסנית דקדוקים חסרי הקשר תכונות של שפות חסרות הקשר סגירות תחת פעולות למת הניפוח לשפות חסרות הקשר צורות נורמליות לדקדוקים חסרי הקשר דו משמעות

רקע נדרש

אמנם הקורס מיועד לקהל ללא ידע רב במדעי המחשב, עם זאת, נדרשת הבנה מתמטית של הנושאים הבאים:

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

לקריאה נוספת

• Michael Sipser, "Introduction to the Theory of Computation", (2nd Ed.) 2006, ISBN 0-534-95097-3
• John Hopcroft, Jeffrey Ullman, "Introduction to Automata Theory, Languages, and Computation", 1979, ISBN 0-201-02988-X