Регулярные языки: два определения и их эквивалентность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 29 промежуточных версий 10 участников)
Строка 1: Строка 1:
 
== Регулярные языки: два определения и их эквивалентность ==
 
== Регулярные языки: два определения и их эквивалентность ==
 
{{Определение
 
{{Определение
 +
|id = REG1
 
|definition =
 
|definition =
Регулярный язык <tex> Reg </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} язык, который может быть получен из букв алфавита при помощи последовательных применений операций объединения, конкатенации или итерации и никаких других, т.е.:
+
'''Множество регулярных языков''' (англ. ''set of regular languages'') <tex>\mathrm{REG}</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots, c_k \right\} </tex> {{---}} множество, которое может быть получено из языков, каждый из которых содержит единственное слово {{---}} <tex>c_i</tex> или <tex>\varepsilon</tex>, и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других, то есть:
 +
* Определим регулярные языки нулевого уровня как <tex> \mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\} </tex>.
 +
* Регулярные языки ненулевого уровня определим рекуррентным соотношением: <tex> \mathrm{R_{i+1}} = \mathrm{R_i} \cup \left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} </tex>.
 +
* Тогда <tex>\mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>.
 +
}}
  
обозначим <tex>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\}</tex>;
+
{{Определение
 +
|definition =
 +
'''Регулярное выражение''' (англ. ''regular expression'') над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} способ порождения языка над <tex>\Sigma</tex>. Определяется рекурсивно следующим образом:
  
определим <tex>R_{i+1}</tex> через <tex>R_i</tex><tex>R_{i+1} = R_i \cup \left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in R_i\right\}</tex>,
+
* Для любого <tex>i</tex> слово <tex>c_i</tex> является регулярным выражением, задающим язык из одного слова <tex>c_i</tex>.
Тогда: <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
+
* <tex>\varepsilon</tex> является регулярным выражением, задающим язык из одной пустой строки, а <tex>\varnothing</tex> {{---}} пустой язык.
 +
* Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\alpha_1)|(\alpha_2)</tex> {{---}} регулярное выражение, задающее <tex>L_1 \bigcup L_2</tex>.
 +
* Если <tex>\alpha_1</tex> и <tex>\alpha_2</tex> являются регулярными выражениями, задающими языки <tex>L_1</tex> и <tex>L_2</tex> соответственно, то <tex>(\alpha_1)(\alpha_2)</tex> {{---}} регулярное выражение, задающее <tex>L_1L_2</tex>.
 +
* Если <tex>\alpha_1</tex> является регулярным выражением, задающим язык <tex>L_1</tex>, то <tex>(\alpha_1)^*</tex> {{---}} регулярное выражение, задающее <tex>L_1^*</tex>.
 +
* Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.
 +
}}
 +
 
 +
{{Утверждение
 +
|statement =
 +
По построению очевидно, что множество языков, порождаемых регулярными выражениями, совпадает со множеством регулярных языков.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = REG2
 
|definition =
 
|definition =
 
Пусть задан алфавит <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex>.
 
Пусть задан алфавит <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex>.
Множество <tex>R</tex> будем называть надрезом, если:
+
Множество <tex>\mathrm{R}</tex> будем называть ''надрегулярным'' множеством над алфавитом <tex> \Sigma </tex>, если:
  
#<tex>R_0 \subset R</tex>, где <tex>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</tex>
+
#<tex>\mathrm{R_0} \subset \mathrm{R}</tex>, где <tex>\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}</tex>,
#<tex> L_1, L_2 \in R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in R</tex>
+
#<tex> L_1, L_2 \in \mathrm{R} \Rightarrow L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}</tex>.
Тогда регулярным языком <tex>Reg'</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрезов: <tex>Reg'=\bigcap\limits_{R - nadrez}R</tex>.
+
 
 +
Тогда '''множеством регулярных языков''' <tex> \mathrm{REG'} </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> называется пересечение всех надрегулярных множеств над этим алфавитом.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Определения 1 и 2 эквивалентны.
+
Классы языков [[#REG1 | <tex>\mathrm{REG}</tex>]] и [[#REG2 | <tex>\mathrm{REG'}</tex>]] над одинаковым алфавитом совпадают.
 
|proof=
 
|proof=
Докажем, что <tex>Reg \subset Reg'</tex> и <tex>Reg' \subset Reg</tex>.
+
Докажем, что <tex>\mathrm{REG} \subseteq \mathrm{REG'}</tex> и <tex>\mathrm{REG'} \subseteq \mathrm{REG}</tex>.
  
*'''<tex>Reg \subset Reg'</tex>'''
+
*'''<tex>\mathrm{REG} \subseteq \mathrm{REG'}</tex>'''
 +
По определению <tex>\mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>. Покажем, что <tex>\bigcup\limits_{i=0}^{\infty}\mathrm{R_i} \subseteq \mathrm{R}</tex>,  где <tex>\mathrm{R}</tex> {{---}} любое надрегулярное множество. Для этого докажем по индукции по <tex>i</tex>, что <tex>\mathrm{R_i} \subseteq \mathrm{R}</tex> для любого <tex>i</tex>.
 +
# База: <tex>i = 0</tex>.
 +
#: <tex>\mathrm{R_0} \subseteq \mathrm{R}</tex> по определению надрегулярного множества.
 +
# Переход: известно, что <tex>\mathrm{R_i} \subseteq \mathrm{R}</tex>, докажем, что <tex>\mathrm{R_{i + 1}} \subseteq \mathrm{R}</tex>.
 +
#: По определению надрегулярного множества для любых <tex>L_1, L_2 \in \mathrm{R_i} \subseteq \mathrm{R}</tex> верны утверждения: <tex>L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}</tex>. То есть: <tex>\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} \subseteq \mathrm{R}</tex>. Вспоминая [[#REG1 | определение]] <tex>\mathrm{R_{i + 1}}</tex> и предположение индукции (<tex>\mathrm{R_i} \subseteq \mathrm{R}</tex>), получаем, что <tex>\mathrm{R_{i + 1}} \subseteq \mathrm{R}</tex>.
 +
Так как <tex>\mathrm{REG} \subseteq R</tex> для любого надрегулярного множества <tex>R</tex>, получаем, что <tex> \mathrm{REG} \subseteq \mathrm{REG'} </tex>.
  
По определению <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>.
+
*'''<tex> \mathrm{REG'} \subseteq \mathrm{REG} </tex>'''
Рассмотрим любое множество <tex> R_i </tex> и любой надрез <tex> R </tex>: <tex>R_i \subset R</tex> (следует из определения <tex>R_i</tex> и определения надреза).
+
Докажем, что <tex> \mathrm{REG} </tex> является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём:
 
+
# <tex> \mathrm{R_0}\subseteq \mathrm{REG} </tex> {{---}} выполнено (по определению <tex> \mathrm{REG} </tex>).
Это верно для  любого надрезa <tex> R </tex>, следовательно <tex> R_i \subset Reg'</tex>. Это выполнено для любого <tex> R_i </tex>, значит <tex> \bigcup\limits_{i=0}^{\infty}R_i \subset Reg' </tex>.
+
# Рассмотрим <tex> L_1, L_2 \in \mathrm{REG} </tex>. Так как <tex> \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}</tex>, то найдутся такие индексы <tex>i</tex> и <tex>j</tex>, что <tex>L_1 \in \mathrm{R_i}</tex> и <tex>L_2 \in \mathrm{R_j}</tex>. Тогда из определения <tex> \mathrm{REG} </tex> следует, что <tex> L_1L_2 \in \mathrm{R_{max(i, j) + 1}}, L_1 \cup L_2\in \mathrm{R_{max(i, j) + 1}}, L_1^* \in \mathrm{R_{i + 1}}</tex>. Так как <tex> \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in \mathrm{REG}, L_1 \cup L_2\in \mathrm{REG}, L_1^* \in \mathrm{REG} </tex>. Следовательно, второе свойство также выполнено.
 
+
Значит, <tex> \mathrm{REG} </tex> {{---}} надрегулярное множество. А так как <tex> \mathrm{REG'}</tex> является пересечением всех надрегулярных множеств, то <tex> \mathrm{REG'} \subseteq \mathrm{REG} </tex>.
*'''<tex>Reg' \subset Reg</tex>'''
+
}}
  
Докажем, что <tex> Reg </tex> является надрезом. Для этого проверим, выполняются ли свойства надреза на нем:
+
== См. также ==
 +
* [[Детерминированные конечные автоматы]]
  
# <tex> R_0 \subset Reg </tex> {{---}} выполнено (следует из определения <tex> Reg </tex>).
+
== Источники информации ==
# Рассмотрим <tex> L_1, L_2 \in Reg </tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex> , то <tex> \exists i </tex>, что <tex> L_1\in R_i </tex> и <tex> \exists j </tex> , что <tex> L_2 \in R_j  </tex>. Тогда из определения <tex> Reg </tex>, следует, что <tex> L_1L_2 \in R_{max(i, j)+1}, L_1 \cup L_2\in R_{max(i, j)+1}, L_1^* \in R_{i + 1}</tex>. Так как <tex>Reg = \bigcup\limits_{i=0}^{\infty}R_i</tex>, то получаем, что <tex> L_1L_2 \in Reg, L_1 \cup L_2\in Reg, L_1^* \in Reg </tex>. Следовательно второе свойство также выполнено.
 
  
Значит, <tex>Reg</tex> {{---}} надрез. А так как <tex>Reg'=\bigcap\limits_{\text{R- nadrez}}R</tex>, то <tex>Reg' \subset Reg</tex>.
+
* [http://en.wikipedia.org/wiki/Regular_language Wikipedia {{---}} Regular language]
}}
+
* [http://en.wikipedia.org/wiki/Regular_expression Wikipedia {{---}} Regular expression]
 +
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия {{---}} Регулярный язык]
 +
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F#.D0.92_.D1.82.D0.B5.D0.BE.D1.80.D0.B8.D0.B8_.D1.84.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.8F.D0.B7.D1.8B.D0.BA.D0.BE.D0.B2 Википедия {{---}} Регулярные выражения]
  
= Литература =
+
[[Категория: Теория формальных языков]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
+
[[Категория: Автоматы и регулярные языки]]

Текущая версия на 19:43, 4 сентября 2022

Регулярные языки: два определения и их эквивалентность

Определение:
Множество регулярных языков (англ. set of regular languages) [math]\mathrm{REG}[/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, \ldots, c_k \right\} [/math] — множество, которое может быть получено из языков, каждый из которых содержит единственное слово — [math]c_i[/math] или [math]\varepsilon[/math], и пустого языка при помощи последовательных применений операций объединения, конкатенации или замыкания Клини и никаких других, то есть:
  • Определим регулярные языки нулевого уровня как [math] \mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\} [/math].
  • Регулярные языки ненулевого уровня определим рекуррентным соотношением: [math] \mathrm{R_{i+1}} = \mathrm{R_i} \cup \left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} [/math].
  • Тогда [math]\mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}[/math].


Определение:
Регулярное выражение (англ. regular expression) над алфавитом [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math] — способ порождения языка над [math]\Sigma[/math]. Определяется рекурсивно следующим образом:
  • Для любого [math]i[/math] слово [math]c_i[/math] является регулярным выражением, задающим язык из одного слова [math]c_i[/math].
  • [math]\varepsilon[/math] является регулярным выражением, задающим язык из одной пустой строки, а [math]\varnothing[/math] — пустой язык.
  • Если [math]\alpha_1[/math] и [math]\alpha_2[/math] являются регулярными выражениями, задающими языки [math]L_1[/math] и [math]L_2[/math] соответственно, то [math](\alpha_1)|(\alpha_2)[/math] — регулярное выражение, задающее [math]L_1 \bigcup L_2[/math].
  • Если [math]\alpha_1[/math] и [math]\alpha_2[/math] являются регулярными выражениями, задающими языки [math]L_1[/math] и [math]L_2[/math] соответственно, то [math](\alpha_1)(\alpha_2)[/math] — регулярное выражение, задающее [math]L_1L_2[/math].
  • Если [math]\alpha_1[/math] является регулярным выражением, задающим язык [math]L_1[/math], то [math](\alpha_1)^*[/math] — регулярное выражение, задающее [math]L_1^*[/math].
  • Операции указаны в порядке возрастания приоритета, при этом скобки повышают приоритет аналогично арифметическим выражениям.


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


Определение:
Пусть задан алфавит [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math].

Множество [math]\mathrm{R}[/math] будем называть надрегулярным множеством над алфавитом [math] \Sigma [/math], если:

  1. [math]\mathrm{R_0} \subset \mathrm{R}[/math], где [math]\mathrm{R_0}=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\}, \ldots, \left\{c_k \right\} \right\}[/math],
  2. [math] L_1, L_2 \in \mathrm{R} \Rightarrow L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}[/math].
Тогда множеством регулярных языков [math] \mathrm{REG'} [/math] над алфавитом [math] \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} [/math] называется пересечение всех надрегулярных множеств над этим алфавитом.


Теорема:
Классы языков [math]\mathrm{REG}[/math] и [math]\mathrm{REG'}[/math] над одинаковым алфавитом совпадают.
Доказательство:
[math]\triangleright[/math]

Докажем, что [math]\mathrm{REG} \subseteq \mathrm{REG'}[/math] и [math]\mathrm{REG'} \subseteq \mathrm{REG}[/math].

  • [math]\mathrm{REG} \subseteq \mathrm{REG'}[/math]

По определению [math]\mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}[/math]. Покажем, что [math]\bigcup\limits_{i=0}^{\infty}\mathrm{R_i} \subseteq \mathrm{R}[/math], где [math]\mathrm{R}[/math] — любое надрегулярное множество. Для этого докажем по индукции по [math]i[/math], что [math]\mathrm{R_i} \subseteq \mathrm{R}[/math] для любого [math]i[/math].

  1. База: [math]i = 0[/math].
    [math]\mathrm{R_0} \subseteq \mathrm{R}[/math] по определению надрегулярного множества.
  2. Переход: известно, что [math]\mathrm{R_i} \subseteq \mathrm{R}[/math], докажем, что [math]\mathrm{R_{i + 1}} \subseteq \mathrm{R}[/math].
    По определению надрегулярного множества для любых [math]L_1, L_2 \in \mathrm{R_i} \subseteq \mathrm{R}[/math] верны утверждения: [math]L_1 \cup L_2 \in \mathrm{R}, L_1L_2 \in \mathrm{R}, L_1^* \in \mathrm{R}[/math]. То есть: [math]\left\{L_1 \cup L_2, L_1L_2, L_1^* | L_1, L_2 \in \mathrm{R_i}\right\} \subseteq \mathrm{R}[/math]. Вспоминая определение [math]\mathrm{R_{i + 1}}[/math] и предположение индукции ([math]\mathrm{R_i} \subseteq \mathrm{R}[/math]), получаем, что [math]\mathrm{R_{i + 1}} \subseteq \mathrm{R}[/math].

Так как [math]\mathrm{REG} \subseteq R[/math] для любого надрегулярного множества [math]R[/math], получаем, что [math] \mathrm{REG} \subseteq \mathrm{REG'} [/math].

  • [math] \mathrm{REG'} \subseteq \mathrm{REG} [/math]

Докажем, что [math] \mathrm{REG} [/math] является надрегулярным множеством. Для этого проверим, выполняются ли свойства надрегулярного множества на нём:

  1. [math] \mathrm{R_0}\subseteq \mathrm{REG} [/math] — выполнено (по определению [math] \mathrm{REG} [/math]).
  2. Рассмотрим [math] L_1, L_2 \in \mathrm{REG} [/math]. Так как [math] \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}\mathrm{R_i}[/math], то найдутся такие индексы [math]i[/math] и [math]j[/math], что [math]L_1 \in \mathrm{R_i}[/math] и [math]L_2 \in \mathrm{R_j}[/math]. Тогда из определения [math] \mathrm{REG} [/math] следует, что [math] L_1L_2 \in \mathrm{R_{max(i, j) + 1}}, L_1 \cup L_2\in \mathrm{R_{max(i, j) + 1}}, L_1^* \in \mathrm{R_{i + 1}}[/math]. Так как [math] \mathrm{REG} = \bigcup\limits_{i=0}^{\infty}R_i[/math], то получаем, что [math] L_1L_2 \in \mathrm{REG}, L_1 \cup L_2\in \mathrm{REG}, L_1^* \in \mathrm{REG} [/math]. Следовательно, второе свойство также выполнено.
Значит, [math] \mathrm{REG} [/math] — надрегулярное множество. А так как [math] \mathrm{REG'}[/math] является пересечением всех надрегулярных множеств, то [math] \mathrm{REG'} \subseteq \mathrm{REG} [/math].
[math]\triangleleft[/math]

См. также

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