Граф состоит из вершин и дуг, помеченных символами входного алфавита. Разрешаются непомеченные дуги.
Некоторые вершины выделены как начальные (в них входит стрелка из «ниоткуда» ) и как заключительные (стрелка выходит в «никуда»). Успешный путь — это путь на графе из начальной вершины в заключительную.
Пометка пути — это последовательность пометок дуг, составляющих путь.
Язык, который описывает граф, это множество пометок всех успешных путей.
Такой граф по сути представляет собой конечный автомат. Будем называть такие графы регулярными.