WikiSort.ru - Не сортированное

Слово формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове ${\displaystyle \alpha }$ называют его длиной и обозначают ${\displaystyle |\alpha |}$ . Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается ${\displaystyle e}$ , ${\displaystyle \varepsilon }$ или ${\displaystyle \Lambda }$ ).

Множество всех слов длины ${\displaystyle n}$ в алфавите ${\displaystyle A}$ обозначают через ${\displaystyle A^{n}}$ , в конечном алфавите число таких слов в точности равно размеру алфавита в степени ${\displaystyle n}$ (${\displaystyle |A^{n}|=|A|^{n}}$ ). Множество всех слов в алфавите ${\displaystyle A}$ (произвольной длины) обозначают через ${\displaystyle A^{*}}$ (звезда Клини), таким образом:

${\displaystyle A^{*}=\bigcup _{n=0}^{+\infty }A^{n}}$ .

На словах над данным алфавитом ${\displaystyle A}$ определена операция конкатенации — последовательного склеивания слов. Множество всех слов в алфавите ${\displaystyle A}$ с операцией конкатенации образует моноид (свободный моноид^[en]). Множество всех непустых слов над алфавитом ${\displaystyle A}$ с операцией конкатенации образует полугруппу.

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Проверить достоверность указанной в статье информации.