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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
== Пустота ==
 
== Пустота ==
  
'''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
+
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] является '''пустым''', если он не содержит ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
  
 
{{Утверждение
 
{{Утверждение
Строка 7: Строка 7:
 
regEmpty
 
regEmpty
 
|statement=
 
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему автомате существует путь из стартового состояния в какое-либо из терминальных.
+
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
  
 
|proof=
 
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, соответствующий этому языку, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
+
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
  
  
Строка 20: Строка 20:
 
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
 
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
  
  boolean dfs(State v) {
+
==== Псевдокод ====
   v.seen = true;
+
 
   if (v.isFinal) {
+
  boolean dfs(State v):
       return false;
+
   v.seen = true
  } 
+
   if v.isFinal:
   for (State u : v.next) {
+
       return false
       if (!u.seen && !dfs(u)) {
+
   for each State u in v.next:
         return false;
+
       if !u.seen && !dfs(u):
      }
+
         return false
  }
+
   return true
   return true;
+
 
}
+
  boolean isEmpty(Automaton a):
+
   for each State v in a:
  boolean isEmpty(Automaton a) {
+
     v.seen = false
   for (State v : a) {
+
   return dfs(a.start)
     v.seen = false;
 
  }
 
   return dfs(a.start);
 
}
 
  
  
 
== Совпадение ==
 
== Совпадение ==
  
'''Совпадение''' двух [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] — свойство, при выполнении которого любое слово, принадлежащее одному из языков, принадлежит второму.
+
Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''', если любое слово или содержится в обоих языках, или не содержится ни в одном из них.
  
Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''идентичными''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется  
+
Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''различимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется  
  
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>,
+
<tex>\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>
  
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>,
+
или
  
где <tex>s_{1}</tex>, <tex>s_{2}</tex> - стартовые состояния.
+
<tex>\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>, <tex>\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle</tex>,
  
На основе заданного отношения разобьём состояния автоматов на классы эквивалентности: состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу тогда и только тогда, когда существует последовательность состояний <tex>p_{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>. Все состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут.
+
где <tex>s_{1}</tex>, <tex>s_{2}</tex> - стартовые состояния, <tex>t_{1}</tex>, <tex>t_{2}</tex> - допускающие состояния, <tex>u_{1}</tex>, <tex>u_{2}</tex> - недопускающие.
 
 
{{Теорема
 
|id=
 
regEqClasses
 
|statement=
 
Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда в любом классе содержатся или только допускающие, или только недопускающие состояния.
 
  
|proof=
+
Все ''бесполезные'' состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут. Введём ''сток'' - специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.
Пусть в каком-либо классе содержатся допускающее состояние <tex>t</tex> и недопускающее <tex>u</tex>. По построению классов эквивалентности, существует последовательность <tex>p_{0}...p_{k}</tex>, где <tex>t = p_{0}</tex>, <tex>u = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex>. Тогда найдётся пара <tex>p_{j}</tex>, <tex>p_{j+1}</tex>: <tex>p_{j}</tex> является допускающим, а <tex>p_{j+1}</tex> - нет. Для определённости, пусть <tex>p_{j}</tex> принадлежит первому автомату, а <tex>p_{j+1}</tex> - второму. Так как эти состояния идентичны, <tex>\exists w</tex>:
 
  
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{j}, \epsilon \rangle</tex>,
 
  
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{j+1}, \epsilon \rangle</tex>.
+
=== Алгоритм проверки языков на совпадение ===
  
Таким образом, слово <tex>w</tex> допускается первым автоматом и не допускается вторым, значит, автоматы неэквивалентны.
+
Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов, вместо них вводится описанный выше сток.
  
  
Пусть в любом классе содержатся только допускающие или только недопускающие состояния. Рассмотрим любую строку <tex>w</tex> и такие состояния <tex>u_{1}</tex> и <tex>u_{2}</tex>, что
+
Пусть <tex>eq(u, v)</tex> - функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма - установка <tex>eq(u, v)</tex> в <tex>false</tex> для всех пар <tex>\langle u, v \rangle</tex>, кроме <tex>\langle s_{1}, s_{2} \rangle</tex>. Также создаётся очередь, в которую помещается пара <tex>\langle s_{1}, s_{2} \rangle</tex>.
  
<tex>\langle s_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle</tex>,
 
  
<tex>\langle s_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle</tex>.
+
Третий шаг алгоритма - [[Обход в ширину|обход в ширину]]. Пусть на текущем шаге из очереди получена пара <tex>\langle u \in A_{1}, v \in A_{2} \rangle</tex>. Тогда для всех символов <tex>c \in \Sigma</tex> рассматриваются пары <tex>\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'</tex>. Если <tex>eq(u', v')</tex> возвращает <tex>false</tex>, данное значение устанавливается в <tex>true</tex>, а в очередь добавляется пара <tex>\langle u', v' \rangle</tex>.
  
Состояния <tex>u_{1}</tex> и <tex>u_{2}</tex> идентичны, следовательно, принадлежат одному классу эквивалентности. Таким образом, любая строка оканчивается либо допускающими состояниями в обоих автоматах, либо в обоих не допускается, значит, автоматы эквивалентны.
 
}}
 
  
 
{{Утверждение
 
{{Утверждение
 
|id=
 
|id=
regEqClasses
+
regEqual
 
|statement=
 
|statement=
Если состояния <tex>p</tex> и <tex>q</tex> принадлежат одному классу эквивалентности, то для любого символа <tex>c</tex> из алфавита <tex>\delta (p, c)</tex> и <tex>\delta (q, c)</tex> также принадлежат одному классу.
+
Автоматы <tex>A_{1}</tex> и <tex>A_{2}</tex> эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары <tex>\langle u, v \rangle</tex>, что <tex>eq(u, v)</tex> возвращает <tex>true</tex> и ровно одно из <tex>\langle u, v \rangle</tex> допускающее.
  
 
|proof=
 
|proof=
Рассмотрим последовательность <tex>p_{0}...p_{k}</tex>, где <tex>p = p_{0}</tex>, <tex>q = p_{k}</tex> и <tex>\forall i = 1..k</tex> <tex>p_{i - 1}</tex> идентично <tex>p_{i}</tex> по строке <tex>w_{i}</tex>. Тогда для последовательности <tex>p'_{0}...p'_{k}</tex>, где <tex>\delta (p, c) = p'_{0}</tex>, <tex>\delta (q, c) = p_{k}</tex> будет верно: <tex>\forall i = 1..k</tex> <tex>p'_{i - 1}</tex> идентично <tex>p'_{i}</tex> по строке <tex>w_{i}c</tex>. Таким образом, <tex>\delta (p, c)</tex> и <tex>\delta (q, c)</tex> также принадлежат одному классу.
+
Пусть такой пары не существует. Возьмём произвольное слово <tex>w</tex> длины <tex>n</tex> и выпишем последовательность пар состояний <tex>\langle u_{i}, v_{i} \rangle</tex>:
}}
+
 
 +
<tex>u_{0} = s_{1}, v_{0} = s_{2}</tex> и <tex>\forall i = 1 .. n</tex> справедливо <tex>\delta_{1} (u_{i-1}, s[i-1]) = u_{i}, \delta_{2} (v_{i-1}, s[i-1]) = v_{i}</tex>. Так как пара <tex>\langle u_{0}, v_{0} \rangle</tex> была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, <tex>eq</tex> для них возвращает <tex>true</tex>. По предположению, или оба состояния <tex>\langle u_{n}, v_{n} \rangle</tex> допускающие в своих автоматах, или оба недопускающие. Таким образом, строка <tex>w</tex> или входит в оба языка, или не входит ни в один.
  
По индукции, утверждение верно и для большего числа переходов.
 
  
=== Алгоритм проверки языков на эквивалентность ===
+
Пусть такая пара <tex>\langle u, v \rangle</tex> существует. Для определённости скажем, что <tex>u \in A_{1}</tex> - допускающее. Рассмотрим строку <tex>w</tex>, состоящую из символов, в результате переходов по которым из <tex>\langle s_{1}, s_{2} \rangle</tex> в процессе обхода в ширину <tex>eq(u, v)</tex> было установлено в <tex>true</tex>. Строка <tex>w</tex> допускается первым автоматом, но не допускается вторым, значит, те не эквивалентны.
 +
}}
  
Первым шагом алгоритма является избавление автоматов от состояний, из которых недостижимы допускающие. Проще всего это реализовать обходом [[Обход в глубину, цвета вершин|в глубину]] или [[Обход в ширину|в ширину]] из допускающих состояний по обратным рёбрам. Все непосещённые состояния затем удаляются из автоматов.
+
==== Псевдокод ====
  
Второй шаг - обход в ширину, объединяющий классы эквивалентности. Изначально каждое состояние принадлежит отдельному классу, кроме двух стартовых, объединённых в один класс. Для определения класса по состоянию используется [[СНМ(наивные реализации)|система непересекающихся множеств]]. Очередь обхода в ширину хранит пары состояний <tex>p_{1} \in A_{1}</tex>, <tex>p_{2} \in A_{2}</tex>, для которых существует строка <tex>w</tex> (для <tex>s_{1}</tex> и <tex>s_{2}</tex> равная <tex>\epsilon</tex>):
+
void revDfs(State v):
 +
  v.seen = true
 +
  for each State u in v.prev:
 +
    if !u.seen:
 +
      revDfs(u)
  
<tex>\langle s_{1}, w \rangle \rightarrow \langle p_{1}, \epsilon \rangle</tex>,
+
void setSink(Automaton a):
 +
  State sink = new State
 +
  for each symbol c in a.alphabet:
 +
    sink.next(c) = sink
 +
  for each State v in a:
 +
    if !v.seen:
 +
      v = sink
  
<tex>\langle s_{2}, w \rangle \rightarrow \langle p_{2}, \epsilon \rangle</tex>.
+
void bfs(Automaton a, Automaton b)
 +
  eq = new bool[a.statesNumber][b.statesNumber]
 +
  fill(eq, false)
 +
  eq[a.start][b.start] = true
 +
  Queue q = new Queue
 +
  q.add((a.start, b.start))
 +
  while !q.isEmpty:
 +
    (v, u) = q.remove()
 +
    for each symbol c in a.alphabet: // a.alphabet == b.alphabet
 +
      v' = v.next(c)
 +
      u' = u.next(c)
 +
      if !eq[v'][u']:
 +
        eq[v'][u'] = true
 +
        q.add((v', u'))
  
Для пары состояний изучаются переходы из них по всем символам алфавита. Пусть <tex>\delta (p_{1}, c) = q_{1}</tex>, <tex>\delta (p_{2}, c) = q_{2}</tex>. Если <tex>q_{1}</tex> и <tex>q_{2}</tex> принадлежат разным классам, их классы объединяются, а пара <tex>\langle q_{1}, q_{2} \rangle</tex> добавляется в очередь.
+
boolean areEqual(Automaton a, Automaton b)
 +
  for each State v in a:
 +
    v.seen = false
 +
  for each State v in a:
 +
    if v.isFinal:
 +
      revDfs(v)
 +
  setSink(a)
 +
  for each State v in b:
 +
    v.seen = false
 +
  for each State v in b:
 +
    if v.isFinal:
 +
      revDfs(v)
 +
  setSink(b)
 +
  bfs(a, b)
 +
  for each State v in a:
 +
    for each State u in b:
 +
      if eq[v][u] && v.isFinal != u.isFinal:
 +
        return false
 +
  return true

Версия 06:36, 26 октября 2011

Пустота

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

Утверждение:
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
[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 each State u in v.next:
     if !u.seen && !dfs(u):
       return false
  return true
boolean isEmpty(Automaton a):
  for each State v in a:
    v.seen = false
  return dfs(a.start)


Совпадение

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

Пусть [math]A_{1}[/math] и [math]A_{2}[/math] - детерминированные конечные автоматы, соответствующие языкам [math]L_{1}[/math] и [math]L_{2}[/math] над одним алфавитом [math]\Sigma[/math], соответственно. Совпадение языков на языке конечных автоматов (эквивалентность) означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния [math]p_{1} \in A_{1}[/math] и [math]p_{2} \in A_{2}[/math] различимыми, если существует строка [math]w[/math] из символов [math]\Sigma[/math], для которой выполняется

[math]\langle p_{1}, w \rangle \rightarrow \langle t_{1}, \epsilon \rangle[/math], [math]\langle p_{2}, w \rangle \rightarrow \langle u_{2}, \epsilon \rangle[/math]

или

[math]\langle p_{1}, w \rangle \rightarrow \langle u_{1}, \epsilon \rangle[/math], [math]\langle p_{2}, w \rangle \rightarrow \langle t_{2}, \epsilon \rangle[/math],

где [math]s_{1}[/math], [math]s_{2}[/math] - стартовые состояния, [math]t_{1}[/math], [math]t_{2}[/math] - допускающие состояния, [math]u_{1}[/math], [math]u_{2}[/math] - недопускающие.

Все бесполезные состояния, из которых не достигаются допускающие, не влияют на множество слов, допускаемых автоматами, поэтому далее они рассматриваться не будут. Введём сток - специальное недопускающее состояние, переходы по всем символам из которого ведут в него самого. Все переходы исходного автомата, которые отсутствовали или вели в бесполезные состояния, направим в сток.


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

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


Пусть [math]eq(u, v)[/math] - функция, принимающая пару состояний из первого и второго автоматов и возвращающая некоторое значение булевского типа. Второй шаг алгоритма - установка [math]eq(u, v)[/math] в [math]false[/math] для всех пар [math]\langle u, v \rangle[/math], кроме [math]\langle s_{1}, s_{2} \rangle[/math]. Также создаётся очередь, в которую помещается пара [math]\langle s_{1}, s_{2} \rangle[/math].


Третий шаг алгоритма - обход в ширину. Пусть на текущем шаге из очереди получена пара [math]\langle u \in A_{1}, v \in A_{2} \rangle[/math]. Тогда для всех символов [math]c \in \Sigma[/math] рассматриваются пары [math]\langle u', v' \rangle : \delta_{1} (u, c) = u', \delta_{2} (v, c) = v'[/math]. Если [math]eq(u', v')[/math] возвращает [math]false[/math], данное значение устанавливается в [math]true[/math], а в очередь добавляется пара [math]\langle u', v' \rangle[/math].


Утверждение:
Автоматы [math]A_{1}[/math] и [math]A_{2}[/math] эквивалентны тогда и только тогда, когда после окончания работы алгоритма не существует такой пары [math]\langle u, v \rangle[/math], что [math]eq(u, v)[/math] возвращает [math]true[/math] и ровно одно из [math]\langle u, v \rangle[/math] допускающее.
[math]\triangleright[/math]

Пусть такой пары не существует. Возьмём произвольное слово [math]w[/math] длины [math]n[/math] и выпишем последовательность пар состояний [math]\langle u_{i}, v_{i} \rangle[/math]:

[math]u_{0} = s_{1}, v_{0} = s_{2}[/math] и [math]\forall i = 1 .. n[/math] справедливо [math]\delta_{1} (u_{i-1}, s[i-1]) = u_{i}, \delta_{2} (v_{i-1}, s[i-1]) = v_{i}[/math]. Так как пара [math]\langle u_{0}, v_{0} \rangle[/math] была в очереди, каждая из последующих пар в процессе алгоритма также побывала в очереди, значит, [math]eq[/math] для них возвращает [math]true[/math]. По предположению, или оба состояния [math]\langle u_{n}, v_{n} \rangle[/math] допускающие в своих автоматах, или оба недопускающие. Таким образом, строка [math]w[/math] или входит в оба языка, или не входит ни в один.


Пусть такая пара [math]\langle u, v \rangle[/math] существует. Для определённости скажем, что [math]u \in A_{1}[/math] - допускающее. Рассмотрим строку [math]w[/math], состоящую из символов, в результате переходов по которым из [math]\langle s_{1}, s_{2} \rangle[/math] в процессе обхода в ширину [math]eq(u, v)[/math] было установлено в [math]true[/math]. Строка [math]w[/math] допускается первым автоматом, но не допускается вторым, значит, те не эквивалентны.
[math]\triangleleft[/math]

Псевдокод

void revDfs(State v):
  v.seen = true
  for each State u in v.prev:
    if !u.seen:
      revDfs(u)
void setSink(Automaton a):
  State sink = new State
  for each symbol c in a.alphabet:
    sink.next(c) = sink
  for each State v in a:
    if !v.seen:
      v = sink
void bfs(Automaton a, Automaton b)
  eq = new bool[a.statesNumber][b.statesNumber]
  fill(eq, false)
  eq[a.start][b.start] = true
  Queue q = new Queue
  q.add((a.start, b.start))
  while !q.isEmpty:
    (v, u) = q.remove()
    for each symbol c in a.alphabet: // a.alphabet == b.alphabet
      v' = v.next(c)
      u' = u.next(c)
      if !eq[v'][u']:
        eq[v'][u'] = true
        q.add((v', u'))
boolean areEqual(Automaton a, Automaton b)
  for each State v in a:
    v.seen = false
  for each State v in a:
    if v.isFinal:
      revDfs(v)
  setSink(a)
  for each State v in b:
    v.seen = false
  for each State v in b:
    if v.isFinal:
      revDfs(v)
  setSink(b)
  bfs(a, b)
  for each State v in a:
    for each State u in b:
      if eq[v][u] && v.isFinal != u.isFinal:
        return false
  return true