Слово (математика)

Слово в дискретній математиці - це будь-який кінцевий впорядкований набір ( кортеж) символів з ​​даного алфавіту. Число символів в слові \ Alpha називають його довжиною і позначають | \ Alpha | . Існує єдине слово довжини 0, зване порожнім словом. Воно не містить жодного символу і позначається буквою e , \ Varepsilon або \ Lambda .

Безліч всіх слів довжини n в алфавіті A позначають через A ^ n ). Безліч всіх слів в алфавіті A (Довільної довжини) позначають через A ^ * . З визначення випливає, що

A ^ * = \ bigcup_ {n = 0} ^ {+ \ infty} A ^ n

На словах в даному алфавіті A визначена операція конкатенації (склеювання слів). Безліч всіх слів в алфавіті A з операцією конкатенації утворює моноід. Безліч всіх непустих слів у алфавіті A з операцією конкатенації утворює напівгруп.