תורת האוטומטים חוקרת מודלים מתמטיים שמדמים חישוב. דוגמה לכך היא האוטומט הסופי, מעין מכונה עם מספר מצבים סופי. עוד דוגמה היא אוטומט המחסנית; זהו אוטומט שיש לו זיכרון נוסף בצורת מחסנית (מבנה נתונים של הערמה).
כאן דנים בעקרונות הבסיסיים של המצבים, המעברים והקלט.
חוקרים פעולות שמבצעים על רצפים של סמלים, כמו חיבור וחיתוך של מילים.
בוחנים איך לשלב שפות פורמליות, להגביל או להרחיב אותן באמצעות פעולות שונות.
ההיררכיה של חומסקי מחלקת את השפות הפורמליות לארבעה סוגים לפי הדקדוקים שיוצרים אותן. כל רמה בהיררכיה מוגבלת יותר מהרמה שמעליה.
ניתן לתאר שפה באמצעות דקדוקים, אוטומטים או ביטויים מתמטיים.
בדקו כיצד משפטים פורמליים נבנים ומפורשים בתוך שפות אלה.
תורת האוטומטים עוסקת במודלים של חישוב. יש מכונות פשוטות שקוראות סדרות של סמלים.
מדברים על מצבים ושינויים בין מצבים.
רואים איך מחברים או חותכים מילים של סמלים.
בודקים איך לשלב קבוצות מילים ולשנותן.
חומסקי חילק שפות ל־4 קבוצות לפי דקדוקים. דקדוק הוא חוק שמייצר מילים.
אפשר להראות שפה בעזרת מכונה, חוקים או ביטויים פשוטים.
בוחנים איך בונים משפטים בשפה וכיצד מפרשים אותם.
תגובות גולשים