Considere um autômato não determinístico NFA = (ܳ Q, ?, ?, F ) , onde ܳQ = representa os estados, ? = {0,1} é o alfabeto, é a função de transição, ܽ? é o estado inicial e F = os estados de aceitação, representados pelo diagrama a seguir
A linguagem desse autômato pode ser descrita como