Слово (формальный язык)

Сло́во формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове называют его длиной и обозначают . Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается , или ).

Множество всех слов длины в алфавите обозначают через , в конечном алфавите число таких слов в точности равно размеру алфавита в степени (). Множество всех слов в алфавите (произвольной длины) обозначают через (звезда Клини), таким образом:

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

Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia

Kembali kehalaman sebelumnya