Изменения

Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных ]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных ]] языков.

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым'''(англ. ''empty''), если он не содержит ни одного слова.

Язык, {{Определение|id=nonempty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, назовём называется '''непустым'''(англ. ''nonempty'').}}

:Пусть язык содержит слово <tex>w</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.

:Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.

Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают'''(англ. ''coincide''), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>L_{1}</tex> '''входит (включается)''' (англ. ''included'') в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.

[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным'''(англ. ''finite''), если принадлежащее ему множество слов конечно.

Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <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>. Топологическую сортировку и поиск цикла можно объединить в один обход, но для наглядности они разделены. ==== Псевдокод ====  Stack topSort(Automaton a): for each State v in a: v.seen = false Stack sorted = new Stack dfsSort(a.start, sorted) return sorted  void dfsSort(State v, Stack sorted): v.seen = true for each State u in v.next: if !u.seen: dfsSort(u, sorted) sorted.push(v)  void reverseDfs(State v): v.canReach = true for each State u in v.prev: if !u.canReach: reverseDfs(u)  boolean dfs(State v): // returns true if and only if there is a cycle v.color = GREY for each State u in v.next: if u.color == GREY: return true if u.canReach && u.color == WHITE && dfs(u): return true v.color = BLACK return false   int words(Automaton a): for each State v in a: v.canReach = false for each State v in a: if v.isFinal: reverseDfs(v) for each State v in a: v.color = WHITE if dfs(a.start): return infinity Stack sorted = topSort(a) paths = new int[a.statesNumber] fill(paths, 0) paths[0] = 1 while !sorted.isEmpty: State v = sorted.pop() for each State u in v.next: paths[u] += paths[v] int result = 0 for each State v in a: if v.isFinal: result += paths[v] return result  == Литература == * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. / Пер. с англ. — Москва: Издательский дом «Вильямс», 2002. — с. 169-177: ISBN 5-8459-0261-4 (рус.)

== Примечания Источики информации ==