Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 37 стр.

определяет регулярные множества. Среди них - регулярные выражения, праволинейные
грамматики, детерминированные и недетерминированные конечные автоматы.
    Пусть Σ - некоторый алфавит. Регулярное множество в алфавите Σ определяется
рекурсивно следующим образом:
    1) 0 - пустое множество;
    2) {ε} - множество из пустой цепочки;
    3) {a} - регулярное множество для каждого элемента a ∈ Σ;
    4) если P и Q - регулярные множества в алфавите Σ, то регулярными являются
       множества:
           а) P ∪ Q
           б) PQ
           в) P*.
    Других регулярных множеств в алфавите Σ нет. Таким образом, некоторое множество
цепочек в заданном алфавите Σ называется регулярным тогда и только тогда, когда либо оно
является одним из множеств: 0, {ε} или {a} для некоторого a ∈ Σ, либо его можно получить
из этих множеств применением конечного числа операций объединения, конкатенации и
итерации.
    Для каждого регулярного множества существует по крайней мере одно регулярное
выражение, обозначающее это множество.
    Язык, распознаваемый конечным автоматом, - это множество цепочек, читаемых
автоматом при переходе из начального состояния в одно из заключительных состояний:

      L(A)={a1 a2 ... an | p0a1 → p1, p1a2 → p2, ..., pn-1an → pn; pn ∈ F}.

    Множество называется регулярным, если существует конечный детерминированный
автомат, распознающий его.

      5.3.3. Операции над регулярными языками
    Так    как      произвольному         конечному    автомату      однозначно соответствует
детерминированный конечный автомат, операции над конечными автоматами эквивалентны
операциям над регулярными множествами, или регулярными языками.
    Известно, что для произвольного конечного автомата можно построить эквивалентный
автомат без циклов в начальных и (или) конечных состояниях.
    Теорема. Для произвольного конечного автомата существует конечный автомат без
циклов в начальном состоянии.
    Доказательство. Пусть A = (К, ∑, δ, p0, F) - произвольный конечный автомат. Построим
автомат:
    A1 = (K ∪ {q0}, Σ, δ ∪ {q0a → pi | p0a → pi ∈ δ}, q0, F ∪ {q0 | p0 ∈ F}).
    Любая цепочка x = a1 a2 ... ak принадлежит языку L(A) тогда и только тогда, когда
существует следующая последовательность команд автомата А:
    p0a1 → p1; p1a2 → p2; . . . ; ph-1ah → ph, ph ∈ F
       и соответствующая ей последовательность команд автомата А1:
    q0a1 → p1; p1a2 → p2; . . . ;         pk-1ak → ph.
    Таким образом, имеем: A = A1.
    Теорема. Для произвольного конечного автомата существует эквивалентный автомат без
циклов в заключительном состоянии.
    Доказательство. Будем считать, что автомат не имеет циклов в начальном состоянии.
Сопоставим заданному произвольному конечному автомату A = (К, ∑, δ, p0, F) новый
автомат A1:
       A1 = (K∪{f}, Σ, δ∪{qja → f | pja → pi∈δ & pi∈F}, p0, {f}∪{p0 | p0 ∈ F}).