Кіріспе
Сызық жиынтықтарындағы бірлік операциясы
Математикалық логика мен информатикада Клейне жұлдызы (немесе Клейне операторы немесе Клейне жабылуы) – бұл сызық жиынтықтарындағы немесе символдар немесе таңбалар жиынтықтарындағы бірлік операциясы. Математикада ол көбінесе еркін моноид құрастырылымы ретінде белгілі. Клейне жұлдызының жиынға қолданылуы деп жазылады. Ол реттегіш өрнектерде кеңінен қолданылады, бұл Стивен Клейне автоматтарды сипаттау үшін енгізген контекст, онда ол "нөл немесе одан көп рет қайталау" дегенді білдіреді. Егер – бұл сызықтар жиынтығы болса, онда – бұл бос сызықты қамтитын және сызықтарды біріктіру операциясы бойынша жабық ең кіші үстін жиынтық ретінде анықталады. Егер – бұл символдар немесе таңбалар жиынтығы болса, онда ол – бұл символдардан құралған барлық сызықтар жиынтығы, бос сызықты қоса алғанда. Жиынды сондай-ақ бос сызықты және –ның кез келген элементтерін тізбектей біріктіру арқылы жасалатын барлық шекті ұзындықтағы сызықтарды қамтитын жиынтық ретінде де сипаттауға болады, бір элементті бірнеше рет пайдалануға рұқсат етіледі. Егер бос жиын немесе бір элементтен тұратын жиын болса, онда ; егер кез келген басқа шекті немесе саналатын шексіз жиын болса, онда – саналатын шексіз жиын. Салдарынан, әрбір формальді тіл шекті немесе саналатын шексіз алфавит бойынша саналатын болады, себебі ол саналатын шексіз жиынның ішкі жиынтығы. Операторлар генеративтік грамматиканың қайта жазу ережелерінде қолданылады.
it is more commonly known as the free monoid construction. The application of the Kleene star to a set is written as It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterize certain automata, where it means "zero or more repetitions". If is a set of strings, then is defined as the smallest superset of that contains the empty string and is closed under the string concatenation operation. If is a set of symbols or characters, then is the set of all strings over symbols in , including the empty string
The set can also be described as the set containing the empty string and all finite length strings that can be generated by concatenating arbitrary elements of , allowing the use of the same element multiple times. If is either the empty set ∅ or the singleton set , then ; if is any other finite set or countably infinite set, then is a countably infinite set. As a consequence, each formal language over a finite or countably infinite alphabet is countable, since it is a subset of the countably infinite set
The operators are used in rewrite rules for generative grammars.
Жалпылау
Сызықтар біріктіру бинарлық операциясы және ε сәйкестік элементі арқылы моноид құрайды. Клин жұлдызы тек сызықтар үшін ғана емес, кез келген моноид үшін анықталған. Нақтырақ айтқанда, (M, ⋅) моноид болсын және S ⊆ M. Онда S* – S жиынын қамтитын M моноидінің ең кіші субмоноиді; яғни, S* M моноидінің бейтарап элементін, S жиынын қамтиды және егер x, y ∈ S* болса, онда x ⋅ y ∈ S*. Бұдан әрі, Клин жұлдызы * операциясын (және одақты) алгебралық құрылымның өзіне толық жұлдызды жартылай сақина түсінігі арқылы қосу арқылы кеңейтіледі.