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