słowa z tego języka, tyle, że zapisane od końca) język słów nie zaczynających się od zera jest regularny, jest nim więc też język słów nie kończących się zerem konkatenacji język słów które można podzielić tak, że początkowa część słowa składa się z naprzemiennie ustawionych zer i jedynek, a końcowa z naprzemiennie ustawionych zer, jedynek i dwójek, jest regularny domknięcia Kleene’ego np. język składający się tylko z 0 i 1 po zastosowaniu domknięcia Kleene’ego jest językiem wszystkich słów zero-jedynkowych.
Deterministyczne automaty skończone (DFA) Do testowania, czy dane słowo należy do danego języka regularnego można zawsze zbudować deterministyczny automat skończony – maszynę, która ma skończoną liczbę stanów, oraz funkcję przejścia, zmieniającą jej stan po przeczytaniu każdego kolejnego znaku w zależności od przeczytanego znaku oraz stanu aktualnego. Niektóre z tych stanów oznaczone są jako akceptujące – tzn. że przeczytany dotychczas fragment jest poprawnym słowem języka, dla którego zbudowano automat.
Rodzinę języków rozpoznawalnych przez automaty skończone oznacza się przez