Изменения

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

* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. / Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177: ISBN 5-8459-0261-4 (рус.)