Языки и детерминированные конечные автоматы

Дадим теперь строгое определение языка, связанного с конкретным ДКА.

Определение 2.4.

Язык, допустимый ДКА M = (Q,,,q₀,F), – это множество всех строк из *, допустимых автоматом М, т.е. L(M) = { |   * и *(q₀, )  F}.

Так как функции  и * являются всюду определенными и каждый шаг работы автомата определяется единственным образом, то любая строка   * после прочтения ее либо допускается (распознается) автоматом, либо отвергается им. Отсюда следует, что

= { |   * и *(q₀, )  F}.

Пример 2.5.

a a, b

q₀ b q­₁ a, b q₂

Этой диаграмме соответствует ДКА, допускающий язык L = {aⁿb| n  0}.

Теорема 2.6.

Пусть M = (Q, , , q₀, F) – детерминированный конечный авто-мат (распознаватель) и пусть D_M – соответствующая диаграмма пе-реходов. В этом случае для любых q_i, q_j  Q и    ⁺ *(q_i, ) = q_j тогда и только тогда, когда в D_M существует путь, помеченный последовательностью символов , из вершины q_i в вершину q_j.

Доказательство.

Проведем его индукцией по длине строки .

Пусть || = 1, т.е.  = а для некоторого a  . Тогда *(q_i­, α) = (q_i, а) = q_j, по определению, соответствует дуге (q_i, q_j), помеченной а, в D_M. Допустим, что для всех  таких, что ||  n, утверждение верно. Пусть || = n + 1, и пусть *(q_i, ) = q_j. Можно положить  = а, где || = n. Тогда для некоторого q_k

*(q_i, ) = q_k и *(q_i­, ) = (q_k­, a) = q_j.

По предположению, равенство *(q_i, ) = q_k эквивалентно существованию пути в D_M из q_i в q_k, помеченному . Кроме того, соотношение *(q_k, a) = q_j эквивалентно существованию дуги (q_k, q_j) с меткой а, что дает нам в D_M путь из q_i в q_j, проходящий через вершину q_k и помеченный строкой a, который соответствует соотношению *(q_i­, ) = q_j. Теорема доказана.

Функция  может быть задана таблицей:

	a1	a2	...	ak	...	an
q0
q1
. . .
qi				qj
. . .
qm

Здесь на пересечении i-й строки и k-го столбца находится q_j тогда и только тогда, когда (q_i, a_k) = q_j.

Если функция  не всюду определенная, то ее можно доопределить так, что соответствующий автомату язык не изменится.

Для любой пары (q, a), для которой (q, a) не определено, положим (q, a) = , где   Q  . Кроме того, для любого а   положим (, a) = .

При этом функция  становится всюду определенной. Так как   Q, то   F, а отсюда следует, что для любой строки   *   L(M) тогда и только тогда, когда в модифицированном ДКА М_ *_(q₀, )  F, что означает, что   L(M_). Следовательно, L(M) = L(M_).

Пример 2.7.

b a, b

a

q₀ q₁ 

b a a b

q₂ q₃ q₄

a b

b a

У приведенного на диаграмме автомата функция переходов не является всюду определенной. Вводя новое состояние , являющееся «ловушкой», мы доопределяем эту функцию (достройка диаграммы показана штрихами).

Определение 2.8.

Язык L называется автоматным, если существует ДКА М такой, что L = L(M).

Таким образом, семейство всех ДКА определяет класс автоматных языков.