NFA הוא מכונת מצבים שבה לכל זוג (מצב, סמל) יכולים להיות אפס, אחד או מספר מעברים, והריצה עשויה להסתעף למספר מצבים בו־זמנית. המכונה מקבלת מחרוזת אם הסתעפות כלשהי של הריצה מסתיימת במצב מקבל. לעיתים קרובות קל יותר לבנות NFA מאשר DFA שקול.
מעבר אפסילון מאפשר לאוטומט לעבור למצב אחר בלי לקרוא אף תו קלט. NFA יכול להשתמש במעברי ε כדי "לקפוץ" בין מצבים באופן חופשי, מה ששימושי להרכבת תת־מכונות. הסימולטור מחשב אוטומטית ε־סגורים בעת ההתקדמות בריצה.
כן. עבור כל NFA קיים DFA שמזהה את אותה שפה, באמצעות בניית קבוצות החזקה (subset construction). ה־DFA המתקבל עשוי להכיל במקרה הגרוע מספר מצבים אקספוננציאלי, אך השפה המזוהה זהה. שני המודלים מגדירים בדיוק את מחלקת השפות הרגולריות.
הסימולטור עוקב אחר קבוצת המצבים הפעילים המלאה בכל שלב, כולל הרחבת ε־סגור. ניתן לראות אילו מצבים פעילים בו־זמנית וכיצד הם מתפתחים ככל שנקרא כל סמל קלט. הקבלה מוצגת לאחר שכל הקלט נקרא ולפחות מצב פעיל אחד הוא מצב מקבל.
NFA מקבל מחרוזת אם קיימת לפחות סדרה אחת של מעברים — בעקבות סמלי הקלט וכל מעברי ε — שמובילה ממצב ההתחלה למצב מקבל לאחר קריאת כל הקלט. מספיק שהסתעפות אחת תצליח; כל שאר ההסתעפויות עשויות לדחות או להיתקע.