Nedetermistický konečný automat
Nedeterministický konečný automat je nejednoznačný. Na rozdíl od deterministického může mít více počátečních stavů. Z každého stavu navíc nemusí být vést hrany pro všechny symboly abecedy. Jednomu slovu tedy může odpovídat více výpočtu (průchodů grafem automatu).
Pokud se při čtení slova automatem dostanu do stavu z něhož není pro další symbol hrana, výpočet pro tento případ končí a slovo v něm nebylo přijato. Pokud neexistuje jiný výpočet pro toto slovo (jiná cesta grafem) který by došel do koncového stavu, slovo nebylo automatem přijato.