אוטומטים ושפות פורמליות
תורת החישוב
אוטומטים סופיים, שפות רגולריות, דקדוקים חופשי-הקשר, אוטומטי מחסנית, ומכונות טיורינג — עם סימולציות אינטראקטיביות לכל צעד.
6יחידות
23שיעורים
0%הושלם
יחידה 10/4
אוטומטים סופיים דטרמיניסטיים (DFA)
הגדרה פורמלית, דיאגרמות מצבים, וסימולציה על מחרוזות קלט
יחידה 20/3
אוטומטים סופיים אי-דטרמיניסטיים (NFA)
מעברי ε, חישוב מקבילי, והמרת NFA ל-DFA
יחידה 30/4
שפות רגולריות
ביטויים רגולריים, משפט Kleene, תכונות סגירות, ולמת ה-pumping
יחידה 40/4
דקדוקים חופשי-הקשר (CFG)
כללי גזירה, עצי parse, רב-משמעות (ambiguity), צורות נורמליות, ואלגוריתם CYK
יחידה 50/3
אוטומטי מחסנית (PDA)
חישוב מבוסס-stack, שקילות עם CFG, ו-PDA דטרמיניסטיים
יחידה 60/5
מכונות טיורינג
חישוב אוניברסלי, הכרעה, וגבולות האלגוריתמים