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

קוד קורס: 10087
2.5 נ"ז

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

דרישות הקדם והדרישות המקבילות בקורס אוטומטים ושפות פורמליות הינן:

דרישות קדם: מתמטיקה בדידה 1 (10078).
דרישות מקבילות: אלגוריתמיקה 1 (10007).