Регулярные языки: два определения и их эквивалентность — различия между версиями
Leugenea (обсуждение | вклад) м |
м (→Регулярные языки: два определения и их эквивалентность) |
||
Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Регулярный язык <tex> Reg </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </tex> {{---}} язык, который может быть получен из букв алфавита при помощи последовательных применений операций объединения, конкатенации или итерации и никаких других, т.е.: | + | '''Регулярный язык''' <tex> Reg </tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, \ldots ,c_k \right\} </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>R_0=\left\{\varnothing, \left\{\varepsilon \right\}, \left\{c_1 \right\}, \left\{c_2 \right\} , \ldots, \left\{c_k \right\} \right\}</tex>; | ||
Строка 17: | Строка 17: | ||
#<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>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> 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 R \Rightarrow L_1 \cup L_2 \in R, L_1L_2 \in R, L_1^* \in 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>Reg'</tex> над алфавитом <tex> \Sigma = \left\{c_1, c_2, ... ,c_k \right\} </tex> называется пересечение всех надрезов: <tex>Reg'=\bigcap\limits_{R - nadrez}R</tex>. |
}} | }} | ||
Версия 00:47, 8 декабря 2011
Регулярные языки: два определения и их эквивалентность
Определение: |
Регулярный язык обозначим ;определим тогда: через : , . | над алфавитом — язык, который может быть получен из букв алфавита при помощи последовательных применений операций объединения, конкатенации или итерации и никаких других, т.е.:
Определение: |
Пусть задан алфавит Множество будем называть надрезом, если:
| .
Теорема: |
Определения 1 и 2 эквивалентны. |
Доказательство: |
Докажем, что и .По определению . Рассмотрим любое множество и любой надрез : (следует из определения и определения надреза).Это верно для любого надрезa , следовательно . Это выполнено для любого , значит .Докажем, что является надрезом. Для этого проверим, выполняются ли свойства надреза на нем:
|
Литература
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)