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