Согласно теореме Клини любому регулярному выражению можно поставить в соответствие конечный автомат, который является формальной моделью алгоритма распознавания лексем, обозначаемых данным регулярным выражением. В наиболее общих терминах конечный автомат-распознаватель определяется конечным множеством характерных для него состояний входного потока и переходов между ними. Изменение состояния происходит при получении символов входного потока из заданного алфавита в соответствии с функцией переходов, которая определяет возможные последующие состояния по входному символу и текущему состоянию. Среди возможных состояний выделяется исходное (начальное) и заключительные (допускающие) состояния в которых конечный автомат-распознаватель может находиться, соответственно, при начале и завершении обработки лексем входного потока. Если входная последовательность символов может порождать последовательность переходов, которая может переводить конечный автомат из начального состояния в одно из заключительных, то она считается допускающей и принадлежит распознаваемому им регулярному множеству.
Конечный автомат распознаватель может быть реализован в детерминированном и недетерминированном варианте. Детерминированный конечный автомат (далее по тексту ДКА) по любому входному символу допускает не более одного перехода из каждого состояния. Поэтому для любого входного символа может существовать только одно допускающее состояние, в которое он может переходить из текущего состояния. Напротив, недетерминированный конечный автомат (далее по тексту НКА) допускает более одного перехода из каждого состояния. Поэтому он одновременно может находиться в нескольких состояниях. Формально ДКА и НКА различаются значением функции переходов. В ДКА значением функции переходов может быть только одно состояние, а в НКА – множество состояний. В общем случае НКА более компактны и легче строятся, но ДКА имеет преимущество по быстродействию. По этой причине для распознавания лексем входного потока по регулярному выражению обычно реализуется ДКА.
В следующем примере рассматривается ДКА для распознавания лексем, обозначаемых регулярным выражением:

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Этому регулярному выражению удовлетворяют бинарные векторы с четным числом нулевых и четным числом единичных разрядов. Например, ему соответствует бинарный вектор 01001000, который содержит две единицы и шесть нулей.
Очевидно, входной алфавит ДКА, реализующего это регулярное выражение, должны составлять символы 0 и 1. Также вполне естественно использовать состояния данного ДКА для подсчета числа нулей и единиц входной последовательности по модулю 2, чтобы фиксировать четное или нечетное число символов 0 или 1 было получено в каждый момент из входного потока. Поэтому актуальными могут быть только четыре состояния, которые можно охарактеризовать и обозначить следующим образом:


Состояние Q1 одновременно является начальным и единственным допускающим. Начальным оно является потому, что до того как будут прочитаны какие-либо входные данные, количество полученных символов 0 и 1 равно нулю, а нуль есть четное число. Это же состояние является единственным допускающим, поскольку только оно в точности удовлетворяет условиям соответствия регулярному выражению, которое должен реализовывать данный ДКА. Чтобы завершить определение ДКА нужно задать функцию переходов между его состояниями. При этом, полезно учесть, что возможно всего 8 переходов по символам 0 и 1 между состояниями, которые различаются либо числом нулей, либо числом единиц. Таким образом, взаимообратные переходы при получении символа 1 имеют место в парах состояний Q1<=>Q2 и Q3<=>Q4. Также взаимообратные переходы имеют место при получении символа 0 в парах состояний Q1<=>Q4 и Q2<=>Q3. Эти наблюдения можно представить в виде следующей двумерной таблицы, обычно называемой таблицей переходов:

Таблица 1    
01
Q1Q4Q2
Q2Q3Q1
Q3Q2Q4
Q4Q1Q3


Столбцы таблицы переходов обозначают символы входного алфавита, а строки соответствуют текущим состояниям ДКА. Элементы каждой строки указывают состояния ДКА, в которые он должен переходить из текущего состояния при получении соответствующих символов входного алфавита. В частности, из первой строки данной таблицы переходов следует, что получение символов 0 и 1 в начальном состоянии Q1 переводит ДКА в состояния Q4 и Q2, соответственно.
При распознавании входной последовательности по таблице переходов легко проследить изменения состояния ДКА с целью определить достигается или нет одно из допускающих состояний. В частности, для бинарного вектора 01001000 с четным числом нулей и единиц рассмотренный ДКА порождает следующую последовательность переходов, где каждый переход помечен вызывающим его символом входного алфавита:

Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1

Эта последовательность переходов завершается допускающим состоянием Q1, следовательно, бинарный вектор 01001000 принадлежит регулярному множеству, распознаваемому рассмотренным ДКА и удовлетворяет приведенному выше регулярному выражению.
В заключение следует отметить, что рассмотренный неформальный способ конструирования ДКА для регулярного выражения основан на частном логическом исследовании проблемы и не является универсальным. Однако существуют формальные алгоритмы построения конечных автоматов по регулярному выражению. В частности, для получения НКА из регулярного выражения используется построение Томпсона, а последующее преобразование НКА в ДКА обеспечивает метод построения подмножеств состояний. Для непосредственного получения ДКА по регулярному выражению применяется алгоритм, основанный на построении синтаксического дерева регулярного выражения.
Перечисленные формальные методы реализованы во всех программах генераторов лексических анализаторов, где для спецификации лексем входного потока используются регулярные выражения. В частности, генератор LEX автоматически конструирует ДКА для лексического анализатора на основе построения синтаксических деревьев регулярных выражений, которые заданы во входном файле спецификации лексем разработчиком лексического анализатора.