Звезда Клини
Поделись знанием:
Х
8 го сентября в сарай к пленным вошел очень важный офицер, судя по почтительности, с которой с ним обращались караульные. Офицер этот, вероятно, штабный, с списком в руках, сделал перекличку всем русским, назвав Пьера: celui qui n'avoue pas son nom [тот, который не говорит своего имени]. И, равнодушно и лениво оглядев всех пленных, он приказал караульному офицеру прилично одеть и прибрать их, прежде чем вести к маршалу. Через час прибыла рота солдат, и Пьера с другими тринадцатью повели на Девичье поле. День был ясный, солнечный после дождя, и воздух был необыкновенно чист. Дым не стлался низом, как в тот день, когда Пьера вывели из гауптвахты Зубовского вала; дым поднимался столбами в чистом воздухе. Огня пожаров нигде не было видно, но со всех сторон поднимались столбы дыма, и вся Москва, все, что только мог видеть Пьер, было одно пожарище. Со всех сторон виднелись пустыри с печами и трубами и изредка обгорелые стены каменных домов. Пьер приглядывался к пожарищам и не узнавал знакомых кварталов города. Кое где виднелись уцелевшие церкви. Кремль, неразрушенный, белел издалека с своими башнями и Иваном Великим. Вблизи весело блестел купол Ново Девичьего монастыря, и особенно звонко слышался оттуда благовест. Благовест этот напомнил Пьеру, что было воскресенье и праздник рождества богородицы. Но казалось, некому было праздновать этот праздник: везде было разоренье пожарища, и из русского народа встречались только изредка оборванные, испуганные люди, которые прятались при виде французов.
Очевидно, русское гнездо было разорено и уничтожено; но за уничтожением этого русского порядка жизни Пьер бессознательно чувствовал, что над этим разоренным гнездом установился свой, совсем другой, но твердый французский порядок. Он чувствовал это по виду тех, бодро и весело, правильными рядами шедших солдат, которые конвоировали его с другими преступниками; он чувствовал это по виду какого то важного французского чиновника в парной коляске, управляемой солдатом, проехавшего ему навстречу. Он это чувствовал по веселым звукам полковой музыки, доносившимся с левой стороны поля, и в особенности он чувствовал и понимал это по тому списку, который, перекликая пленных, прочел нынче утром приезжавший французский офицер. Пьер был взят одними солдатами, отведен в одно, в другое место с десятками других людей; казалось, они могли бы забыть про него, смешать его с другими. Но нет: ответы его, данные на допросе, вернулись к нему в форме наименования его: celui qui n'avoue pas son nom. И под этим названием, которое страшно было Пьеру, его теперь вели куда то, с несомненной уверенностью, написанною на их лицах, что все остальные пленные и он были те самые, которых нужно, и что их ведут туда, куда нужно. Пьер чувствовал себя ничтожной щепкой, попавшей в колеса неизвестной ему, но правильно действующей машины.
Пьера с другими преступниками привели на правую сторону Девичьего поля, недалеко от монастыря, к большому белому дому с огромным садом. Это был дом князя Щербатова, в котором Пьер часто прежде бывал у хозяина и в котором теперь, как он узнал из разговора солдат, стоял маршал, герцог Экмюльский.
Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях.
- Если V — множество строк
- то V* — минимальное надмножество множества V, которое содержит ε (пустую строку) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V.
- Если V — множество символов
- то V* — множество всех строк из символов из V с добавлением пустой строки.
Содержание
Определение
Степень множества
 |
Вкратце: <math>
i </math>-я степень множества <math>V</math> — это конкатенация множества <math>V</math> с самим собой <math>i-1</math> раз. |
Нулевая степень любого множества неизменна:
- <math> V^0 = \left\{\varepsilon \right\} </math>.
Остальные степени определяются рекурсивно:
- <math> V^i = V^{i-1} V = \left\{wv \left|\, w \in V^{i-1} \land v \in V \right. \right\} </math>, где <math>i \in \N</math>.
- Если <math>V</math> — множество символов
- то <math>V^i</math> — множество строк длиной <math>i</math> символов, взятых из <math>V</math>.
Звезда Клини
Замыкание Клини множества <math> V </math> есть
- <math>
V^* = \bigcup_{i=0}^{\infty} V^i </math>.
То есть это множество всех строк конечной длины́, порождённое элементами множества <math> V </math>.
Плюс Клини
Есть операция, аналогичная звезде Клини, — плюс Клини:
- <math>
V^+ = \bigcup_{i=1}^{\infty} V^i </math>. Как видим, отличается тем, что пропущено <math> V^0 </math>, содержащее пустую строку.
Свойства
- Связь операций:
- <math> V^+ = V^*V </math>
- <math> V^+ = V^* \Leftrightarrow \varepsilon \in V</math>
- Идемпотентность:
- <math> V^* = {V^*}^* </math>.
- Замыкание Клини включает в себя порождающее множество:
- <math> V \subseteq V^* </math>.
- Замыкание Клини всегда содержит пустую строку:
- <math> \varepsilon \in V^* </math>.
- <math>
\left|V^* \right| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \ne V \ne \{\varepsilon\} </math>.
Примеры
- Для множества строк
- {"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}.
- Для множества символов
- {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", …}.
- Для множества из пустой строки
- <math>
\left\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\} </math>.
- Для пустого множества
- <math> \varnothing^* = \left\{\varepsilon \right\} </math>.
- <math> \varnothing^+ = \varnothing^* \varnothing = \varnothing </math>.
Обобщение
Стро́ки образуют моноид по конкатенации с нейтральным элементом <math>\varepsilon</math>. Таким образом, определение звезды́ Клини можно распространить на любой моноид.
См. также
Напишите отзыв о статье "Звезда Клини"
Литература
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. — 3rd Edition. — 2006. — 535 p. — ISBN 0321462254.
- Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung. — 2., erw. — Springer-Verlag, 2002. — С. 27—29. — ISBN 3-540-42624-8.
Отрывок, характеризующий Звезда Клини
Х
8 го сентября в сарай к пленным вошел очень важный офицер, судя по почтительности, с которой с ним обращались караульные. Офицер этот, вероятно, штабный, с списком в руках, сделал перекличку всем русским, назвав Пьера: celui qui n'avoue pas son nom [тот, который не говорит своего имени]. И, равнодушно и лениво оглядев всех пленных, он приказал караульному офицеру прилично одеть и прибрать их, прежде чем вести к маршалу. Через час прибыла рота солдат, и Пьера с другими тринадцатью повели на Девичье поле. День был ясный, солнечный после дождя, и воздух был необыкновенно чист. Дым не стлался низом, как в тот день, когда Пьера вывели из гауптвахты Зубовского вала; дым поднимался столбами в чистом воздухе. Огня пожаров нигде не было видно, но со всех сторон поднимались столбы дыма, и вся Москва, все, что только мог видеть Пьер, было одно пожарище. Со всех сторон виднелись пустыри с печами и трубами и изредка обгорелые стены каменных домов. Пьер приглядывался к пожарищам и не узнавал знакомых кварталов города. Кое где виднелись уцелевшие церкви. Кремль, неразрушенный, белел издалека с своими башнями и Иваном Великим. Вблизи весело блестел купол Ново Девичьего монастыря, и особенно звонко слышался оттуда благовест. Благовест этот напомнил Пьеру, что было воскресенье и праздник рождества богородицы. Но казалось, некому было праздновать этот праздник: везде было разоренье пожарища, и из русского народа встречались только изредка оборванные, испуганные люди, которые прятались при виде французов.
Очевидно, русское гнездо было разорено и уничтожено; но за уничтожением этого русского порядка жизни Пьер бессознательно чувствовал, что над этим разоренным гнездом установился свой, совсем другой, но твердый французский порядок. Он чувствовал это по виду тех, бодро и весело, правильными рядами шедших солдат, которые конвоировали его с другими преступниками; он чувствовал это по виду какого то важного французского чиновника в парной коляске, управляемой солдатом, проехавшего ему навстречу. Он это чувствовал по веселым звукам полковой музыки, доносившимся с левой стороны поля, и в особенности он чувствовал и понимал это по тому списку, который, перекликая пленных, прочел нынче утром приезжавший французский офицер. Пьер был взят одними солдатами, отведен в одно, в другое место с десятками других людей; казалось, они могли бы забыть про него, смешать его с другими. Но нет: ответы его, данные на допросе, вернулись к нему в форме наименования его: celui qui n'avoue pas son nom. И под этим названием, которое страшно было Пьеру, его теперь вели куда то, с несомненной уверенностью, написанною на их лицах, что все остальные пленные и он были те самые, которых нужно, и что их ведут туда, куда нужно. Пьер чувствовал себя ничтожной щепкой, попавшей в колеса неизвестной ему, но правильно действующей машины.
Пьера с другими преступниками привели на правую сторону Девичьего поля, недалеко от монастыря, к большому белому дому с огромным садом. Это был дом князя Щербатова, в котором Пьер часто прежде бывал у хозяина и в котором теперь, как он узнал из разговора солдат, стоял маршал, герцог Экмюльский.
