כל מה שרצית לדעת על אוטומט סופי לא דטרמיניסטי:
אוטומט סופי לא דטרמיניסטי הוא מודל מתמטי המהווה הכללה של אוטומט סופי דטרמיניסטי בכך שהוא מאפשר בחירה בין מספר דרכי פעולה עבור קלט נתון, בניגוד לדרך הפעולה היחידה אליה מחויב אוטומט דטרמיניסטי.
המודל הוצג לראשונה על ידי מיכאל רבין ודנה סקוט במאמר מ1959.
ההכללה של האוטומט הסופי הדטרמיניסטי מתבטאת בשלוש הרחבות עיקריות:

עבור כל מצב של האוטומט ואות קלט נתונה, האוטומט הלא דטרמיניסטי יכול לעבור למספר מצבים, ולא למצב יחיד כאוטומט הדטרמיניסטי.
לאוטומט מוספת האפשרות של "מסע " – מעבר ממצב אחד למשנהו מבלי שתיקלט אות קלט כלשהי.
לאוטומט מוספת האפשרות לבחור בין מספר מצבים התחלתיים.

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

נלקח מויקיפדיה

הגדרות נוספות הקשורות לאוטומט סופי לא דטרמיניסטי:
•אוטומטים