Przykład automatu deterministycznego (3) Automat służący do sprawdzania czy dane słowo binarne ma lub znaków mógłby wyglądać tak: Stany to aż do i stan ZaDługie. Stan początkowy to Jeśli automat jest w stanie to po przeczytaniu dowolnego znaku przechodzi w stan Jeśli automat jest w stanie to po przeczytaniu dowolnego znaku przechodzi w stan ZaDługie. Jeśli automat jest w stanie ZaDługie, po przeczytaniu dowolnego znaku pozostaje w stanie ZaDługie. Akceptujące są stany i
Twierdzenie Kleene’ego Twierdzenie Kleene’ego dokładnie określa relacje pomiędzy rodzinami języków (rozpoznawalnych) i (regularnych). Mianowicie, dla dowolnego alfabetu (skończonego) zachodzi Dowód tego twierdzenia przeprowadza się na zasadzie obustronnej inkluzji (ale jest on długi i zostaje pominięty).
Główną konsekwencją tego dowodu jest, wspomniana już wcześniej, bezpośrednia zależność języków regularnych i automatów skończonych. Zatem dla każdego języka regularnego można stworzyć automat skończony i, analogicznie, każdy automat skończony rozpoznaje język regularny.