20242 אוטומטים ושפות פורמליות
20242 אוטומטים ושפות פורמליות
6 נקודות זכות ברמה רגילה
שיוך: מדעים / מדעי המחשב
ידע קודם דרוש: הקורסים מבוא למדעי המחשב ושפת Java או מבוא למדעי המחשב או מבוא למדעי המחשב ושפת פסקל, מתמטיקה דיסקרטית. ידע קודם מומלץ: הקורסים חשבון אינפיניטסימלי 1, אלגברה לינארית 1.
פיתוח הקורס: פרופ' שמואל זקס, פרופ' נסים פרנסיז (כתיבה), פרופ' יהודית גל-עזר, בני פרידמן, ד"ר ענת לרנר, יוסי קאופמן, מיכל ארמוני; בת-שבע כהן (עריכה)
יועצים: פרופ' דוד הראל, פרופ' עמירם יהודאי, פרופ' יעקב שוויקה
הקורס כלול בסדרה של קורסים המקנים את היסודות התאורטיים במדעי המחשב, ומיועד לדון בבעיות מתמטיות בסיסיות המונחות ביסודם של מדעי המחשב.
מטרת הקורס היא הכרת המודלים החישוביים היסודיים והשוואת כוח החישוב שלהם, ובמקביל – הכרת המשפחות היסודיות של שפות פורמליות.
יחידות הלימוד
|
יחידה 1 |
מושגים בסיסיים |
|
יחידה 2 |
אוטומט סופי דטרמיניסטי |
|
יחידה 3 |
אוטומט סופי לא-דטרמיניסטי וביטויים רגולריים |
|
יחידה 4 |
תכונות של שפות רגולריות |
|
יחידה 5 |
אפיון אלגברי של השפות הרגולריות |
|
יחידה 6 |
דקדוקים |
|
יחידה 7 |
פישוטים וצורות נורמליות של דקדוקים חופשיי-הקשר |
|
יחידה 8 |
אוטומט-מחסנית |
|
יחידה 9 |
תכונות של שפות חופשיות-הקשר |
1