Изменения

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <tex>paths(v)</tex>, задающую число различных путей из <tex>s</tex> в <tex>v</tex>; <tex>paths(s) = 1</tex>. Заметим, что если известны значения <tex>paths(u)</tex> для всех <tex>u</tex>, из которых существует переход в <tex>v</tex>, то <tex>paths(v) = \sum\limits_{u}paths(u)</tex>. Количеством слов в языке будет сумма <tex>paths(t)</tex> для всех допускающих <tex>t</tex>.

== Литература ==