A construção composicional de um sistema de estados finitos real pode utilizar as três formas de composição: sequencial (execução da próxima componente depende da terminação da anterior), concorrente (componentes são independentes e podem ser processadas ao mesmo tempo) e não-determinista (próxima componente resulta da escolha entre diversas alternativas).

Qualquer AF determinístico pode ser simulado por um AF não-determinístico. O AF 1 é não-determinístico e o AF 2 é determinístico. Ambos são capazes de reconhecer uma linguagem formada por {a, b}, mas as palavras que o AF1 reconhece começam com a ou b e as palavras que AF2 reconhece começam com ab.

O AF é um modelo computacional muito utilizado em estudos teórico-formais relativos à definição de linguagens formais, compiladores etc. Possui um número finito e predefinido de estados. Se algum AF reconhece uma linguagem, esta é denominada linguagem regular.

Dependendo do estado corrente e do símbolo lido, os AFs podem ser determinísticos, quando podem assumir como próximo estado um único estado ou não-determinísticos, quando podem assumir um conjunto de estados alternativos.

A classe dos AFs determinísticos é equivalente à classe dos AFs não-determinísticos. O AF 1 é determinístico e o AF 2 é não determinístico. Ambos são capazes de reconhecer uma linguagem formada por {a, b} que possuem aa ou bb como subpalavra.