Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)

Пустота

Пустота регулярного языка — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём непустым.

Утверждение:

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

[math]\triangleright[/math]

Пусть язык содержит слово [math]w[/math]. Любой автомат [math]A[/math], соответствующий этому языку, должен допускать [math]w[/math]. Тогда при переходе из стартового состояния [math]A[/math] по символам [math]w[/math] получится путь, оканчивающийся в одной из терминальных вершин. Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.

[math]\triangleleft[/math]

Алгоритм проверки языка на пустоту

Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм обхода в глубину. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.

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);
}