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