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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Пустота == '''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярно...»)
 
(не показаны 43 промежуточные версии 9 участников)
Строка 1: Строка 1:
== Пустота ==
+
Для различных операций с [[Регулярные языки: два определения и их эквивалентность|регулярными языками]] полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности [[Детерминированные_конечные_автоматы#Автоматные_языки | автоматных]] и [[Регулярные языки:_два определения_и_их_эквивалентность#REG1 | регулярных]]  языков.
  
'''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
+
== Пустота регулярного языка ==
  
{{Утверждение
+
{{Определение
 +
|id=empty
 +
|definition=
 +
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''пустым''' (англ. ''empty''), если он не содержит ни одного слова.
 +
}}
 +
 
 +
{{Определение
 +
|id=nonempty
 +
|definition=
 +
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] содержащий хотя бы одно слово, называется '''непустым''' (англ. ''nonempty'').
 +
}}
 +
 
 +
{{Теорема
 
|id=
 
|id=
 
regEmpty
 
regEmpty
 
|statement=
 
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему автомате существует путь из стартового состояния в какое-либо из терминальных.
+
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
  
 
|proof=
 
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, соответствующий этому языку, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
+
<tex>\Rightarrow</tex>
  
 +
:Пусть язык содержит слово <tex>w</tex>. Любой [[Детерминированные конечные автоматы| детерминированный конечный автомат]] <tex>A</tex>, задающий этот язык, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одном из терминальных состояний.
  
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
+
<tex>\Leftarrow</tex>
 +
:Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на переходах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
 
}}
 
}}
  
Строка 20: Строка 34:
 
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
 
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
  
boolean dfs(State v) {
+
== Совпадение регулярных языков ==
  v.seen = true;
+
 
  if (v.isFinal) {
+
{{Определение
      return false;
+
|id=equal
  } 
+
|definition=
  for (State u : v.next) {
+
Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''' (англ. ''coincide''), если любое слово или содержится в обоих языках, или не содержится ни в одном из них.
      if (!u.seen && !dfs(u)) {
+
}}
        return false;
+
 
      }
+
Для проверки совпадения языков достаточно запустить алгоритм проверки [[Эквивалентность_состояний_ДКА|эквивалентности]] задающих их автоматов.
  }
+
 
  return true;
+
=== Пример проверки на совпадение регулярных языков===
}
+
Для того, чтобы узнать равен ли язык своему замыканию Клини, нужно проверить на [[Эквивалентность_состояний_ДКА|эквивалентность]] автомат, задающий язык, и автомат, задающий замыкание Клини языка. Если автоматы эквивалентны, то язык равен своему замыканию Клини.
+
 
boolean isEmpty(Automaton a) {
+
== Включение одного регулярного языка в другой ==
  for (State v : a) {
+
 
    v.seen = false;
+
{{Определение
  }
+
|id=inclusion
  return dfs(a.start);
+
|definition=
}
+
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] <tex>L_{1}</tex> '''входит (включается)''' (англ. ''included'') в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.
 +
}}
 +
 
 +
Пусть автомат <tex>M_1</tex> задаёт язык <tex>L_1</tex>, а автомат <tex>M_2</tex> — язык <tex>L_1 \cap L_2</tex>. Для проверки включения <tex>L_1</tex> в <tex>L_2</tex> достаточно проверить [[Эквивалентность_состояний_ДКА|эквивалентность]] <tex>M_1</tex> и <tex>M_2</tex>.
 +
 
 +
== Конечность регулярного языка, подсчёт числа слов ==
 +
 
 +
{{Определение
 +
|id=finite
 +
|definition=
 +
[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным''' (англ. ''finite''), если принадлежащее ему множество слов конечно.
 +
}}
 +
 
 +
{{Теорема
 +
|id=
 +
regFinite
 +
|statement=
 +
[[Детерминированные конечные автоматы|Детерминированный конечный автомат]] <tex>A_{1}</tex> задаёт конечный язык тогда и только тогда, когда в <tex>A_{1}</tex> не существует состояния <tex>v</tex>, для которого выполняются три условия:
 +
* <tex>v</tex> достижимо из стартового состояния <tex>s</tex>;
 +
* из <tex>v</tex> достижимо какое-либо из допускающих состояний;
 +
* из <tex>v</tex> по одному или более переходам достижимо <tex>v</tex>.
 +
 
 +
|proof=
 +
Пусть такое состояние <tex>v</tex> существует, а строки <tex>x, y, z</tex> таковы, что <tex>\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle</tex>, <tex>t</tex> — допускающее, <tex>y</tex> — непустая. Рассмотрим строки вида <tex>xy^{k}z, k \in \mathbb{N}</tex>. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.
 +
 
 +
 
 +
Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено <tex>n! | \Sigma |^{n-1}</tex>, где <tex>n</tex> — количество состояний автомата: <tex>n!</tex> — количество перестановок состояний, <tex>| \Sigma |^{n-1}</tex> — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
 +
}}
 +
 
 +
=== Алгоритм нахождения числа слов в языке ===
 +
 
 +
Доказанное утверждение позволяет свести задачу поиска числа слов в языке к поиску количества различных путей в ациклическом графе. Сначала с помощью [[Обход в глубину, цвета вершин|обхода в глубину]] по обратным рёбрам определим '''полезные''' состояния, из которых достижимо хотя бы одно допускающее. Затем найдём любой цикл, состояния которого полезны, достижимый из старта; при нахождении констатируем бесконечность языка. Пусть язык конечен; тогда отсортируем автомат [[Использование обхода в глубину для топологической сортировки|топологически]]. Введём функцию <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
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Автоматы и регулярные языки]]
 +
[[Категория: Свойства конечных автоматов]]

Версия 22:48, 31 января 2019

Для различных операций с регулярными языками полезно знать некоторые их свойства. Как правило, в доказательствах этих свойств используется факт из теоремы Клини об эквивалентности автоматных и регулярных языков.

Пустота регулярного языка

Определение:
Регулярный язык называется пустым (англ. empty), если он не содержит ни одного слова.


Определение:
Регулярный язык содержащий хотя бы одно слово, называется непустым (англ. nonempty).


Теорема:
Регулярный язык является непустым тогда и только тогда, когда в любом задающем его автомате существует путь из стартового состояния в какое-либо из терминальных.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

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

[math]\Leftarrow[/math]

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

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

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

Совпадение регулярных языков

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


Для проверки совпадения языков достаточно запустить алгоритм проверки эквивалентности задающих их автоматов.

Пример проверки на совпадение регулярных языков

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

Включение одного регулярного языка в другой

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


Пусть автомат [math]M_1[/math] задаёт язык [math]L_1[/math], а автомат [math]M_2[/math] — язык [math]L_1 \cap L_2[/math]. Для проверки включения [math]L_1[/math] в [math]L_2[/math] достаточно проверить эквивалентность [math]M_1[/math] и [math]M_2[/math].

Конечность регулярного языка, подсчёт числа слов

Определение:
Регулярный язык называется конечным (англ. finite), если принадлежащее ему множество слов конечно.


Теорема:
Детерминированный конечный автомат [math]A_{1}[/math] задаёт конечный язык тогда и только тогда, когда в [math]A_{1}[/math] не существует состояния [math]v[/math], для которого выполняются три условия:
  • [math]v[/math] достижимо из стартового состояния [math]s[/math];
  • из [math]v[/math] достижимо какое-либо из допускающих состояний;
  • из [math]v[/math] по одному или более переходам достижимо [math]v[/math].
Доказательство:
[math]\triangleright[/math]

Пусть такое состояние [math]v[/math] существует, а строки [math]x, y, z[/math] таковы, что [math]\langle s, xyz \rangle \vdash ^{*} \langle v, yz \rangle \vdash ^{*} \langle v, z \rangle \vdash ^{*} \langle t, \epsilon \rangle[/math], [math]t[/math] — допускающее, [math]y[/math] — непустая. Рассмотрим строки вида [math]xy^{k}z, k \in \mathbb{N}[/math]. Их бесконечное количество, и все они, как легко увидеть, допускаются автоматом. Значит, язык бесконечен.


Пусть такого состояния не существует. Тогда любой путь из стартового состояния в какое-либо из допускающих является простым. Количество слов в языке равно количеству таких путей; количество путей, в свою очередь, ограничено [math]n! | \Sigma |^{n-1}[/math], где [math]n[/math] — количество состояний автомата: [math]n![/math] — количество перестановок состояний, [math]| \Sigma |^{n-1}[/math] — количество совокупностей переходов по символам между ними. Таким образом, язык конечен.
[math]\triangleleft[/math]

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

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

См. также

Источики информации

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