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

  • Разделы:

    У этого термина существуют и другие значения, см. Слово (значения).

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

    Множество всех слов длины n{displaystyle n} в алфавите A{displaystyle A} обозначают через An{displaystyle A^{n}} (см. также Декартово произведение множеств). Множество всех слов в алфавите A{displaystyle A} (произвольной длины) обозначают через A∗{displaystyle A^{*}}. Из определения следует, что

    A∗=⋃n=0+∞An{displaystyle A^{*}=bigcup _{n=0}^{+infty }A^{n}}

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

    Шаблон:Нет интервики