Зірка Кліні

Зірка Кліні (або замикання Кліні) в математичній логіці та інформатики - унарний операція над безліччю рядків або символів. Замикання Кліні безлічі V позначається V *. Широко застосовується в регулярних виразах, на прикладі яких було введено Стівеном Кліні для опису деяких автоматів .

Якщо V - безліч рядків
то V * - мінімальне надмножество безлічі V, яке містить ε ( порожній рядок) і замкнуто щодо конкатенації. Це також безліч всіх рядків, отриманих конкатенації нуля або більше рядків з V.
Якщо V - безліч символів
то V * - безліч всіх рядків із символів з ​​V з додаванням порожнього рядка.

1. Визначення

1.1. Ступінь безлічі

Нульова ступінь будь-якого безлічі незмінна:

V ^ 0 = \ left \ {\ varepsilon \ right \} .

Решта мірі визначаються рекурсивно :

V ^ i = V ^ {i-1} V = \ left \ {wv \ left | \, w \ in V ^ {i-1} \ land v \ in V \ right. \ Right \} , Де i \ in \ N .
Якщо V - Безліч символів
то V ^ i - Безліч рядків довжиною i символів, взятих з V .

1.2. Зірка Кліні

Замикання Кліні безлічі V є

V ^ * = \ bigcup_ {i = 0} ^ {\ infty} V ^ i .

Тобто це множина всіх рядків кінцевої довжини, породжене елементами безлічі V .

1.3. Плюс Кліні

Є операція, аналогічна зірці Кліні, - плюс Кліні:

V ^ + = \ bigcup_ {i = 1} ^ {\ infty} V ^ i .

Як бачимо, відрізняється тим, що пропущено V ^ 0 , Що містить порожню рядок.

2. Властивості

V ^ * = {V ^ *} ^ * .
  • Замикання Кліні включає в себе породжує безліч:
V \ subseteq V ^ * .
  • Замикання Кліні завжди містить порожню рядок:
\ Varepsilon \ in V ^ * .
\ Left | V ^ * \ right | = \ left | V ^ + \ right | = \ alef_0 \ Leftarrow \ varnothing \ ne V \ ne \ {\ varepsilon \} .

3. Приклади

Для безлічі рядків
{"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", ...}.
Для безлічі з порожнього рядка
\ Left \ {\ varepsilon \ right \} ^ * = \ left \ {\ varepsilon \ right \} ^ + = \ left \ {\ varepsilon \ right \} .
Для порожнього безлічі
\ Varnothing ^ * = \ left \ {\ varepsilon \ right \} .
\ Varnothing ^ + = \ varnothing ^ * \ varnothing = \ varnothing .

4. Узагальнення

Рядки утворюють моноід по конкатенації з нейтральним елементом \ Varepsilon . Таким чином, визначення зірки Кліні можна поширити на будь моноід.

Література

  • 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 Einfhrung. - 2., Erw. - Springer-Verlag, 2002. - С. 27-29. - ISBN 3-540-42624-8