תורת האוטומטים

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