Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)
Пустота
Пустота регулярного языка — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём непустым.
Утверждение: |
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему автомате существует путь из стартового состояния в какое-либо из терминальных. |
Пусть язык содержит слово . Любой автомат , соответствующий этому языку, должен допускать . Тогда при переходе из стартового состояния по символам получится путь, оканчивающийся в одной из терминальных вершин.
|
Алгоритм проверки языка на пустоту
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
boolean dfs(State v) { v.seen = true; if (v.isFinal) { return false; } for (State u : v.next) { if (!u.seen && !dfs(u)) { return false; } } return true; } boolean isEmpty(Automaton a) { for (State v : a) { v.seen = false; } return dfs(a.start); }
Совпадение
Совпадение двух регулярных языков — свойство, при выполнении которого любое слово, принадлежащее одному из языков, принадлежит второму.
Пусть
и - детерминированные конечные автоматы, соответствующие языкам и над одним алфавитом , соответственно. Совпадение языков на языке конечных автоматов (эквивалентность) означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния и идентичными, если существует строка из символов , для которой выполняется,
,
где
, - стартовые состояния.На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния
и принадлежат одному классу тогда и только тогда, когда существует последовательность состояний , где , и идентично . Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут.Утверждение: |
Автоматы и эквивалентны тогда и только тогда, когда в любом классе содержатся или только допускающие, или только недопускающие состояния. |
Пусть в каком-либо классе содержатся допускающее состояние и недопускающее . По построению классов эквивалентности, существует последовательность , где , и идентично . Тогда найдётся пара , : является допускающим, а - нет. Для определённости, пусть принадлежит первому автомату, а - второму. Так как эти состояния идентичны, :, . Таким образом, слово допускается первым автоматом и не допускается вторым, значит, автоматы неэквивалентны.
, Состояния . и идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями в обоих автоматах, либо в обоих не допускается, значит, автоматы эквивалентны. |
Утверждение: |
Если состояния и принадлежат одному классу эквивалентности, то для любого символа из алфавита и также принадлежат одному классу. |
Рассмотрим последовательность | , где , и идентично по строке . Тогда для последовательности , где , будет верно: идентично по строке . Таким образом, и также принадлежат одному классу.
По индукции, утверждение верно и для большего числа переходов.
Алгоритм проверки языков на эквивалентность
Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом в глубину или в ширину из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов.
Второй шаг - обход в ширину, объединяющий классы эквивалентности. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется система непересекающихся множеств. Очередь обхода в ширину хранит пары состояний , , для которых существует строка (для и равная ):
,
.
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть
, .