Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками

Определение:

Алфавит — конечное непустое множество. Условимся обозначать алфавит символом [math]\Sigma[/math].

Наиболее часто используются следующие алфавиты:

1. [math]\Sigma=\{0, 1\}[/math] — бинарный или двоичный алфавит.
2. [math]\Sigma=\{a, b, ...,z\}[/math] — множество строчных букв английского алфавита.

Определение:

Слово (цепочка) — конечная последовательность символов некоторого алфавита.

Определение:

Пустая цепочка — цепочка, не содержащая ни одного символа. Эту цепочку, обозначаемую [math] \varepsilon [/math], можно рассматривать как цепочку в любом алфавите.

Определение:

Длина цепочки — число символов в цепочке. Длину некоторой цепочки [math]w[/math] обычно обозначают [math]|w|[/math].

Определение:

[math]\Sigma^k[/math] — множество цепочек длины [math]k[/math] над алфавитом [math]\Sigma[/math].

Определение:

[math]\Sigma^* = \bigcup \limits _{k=0}^\infty \Sigma^k[/math] — множество всех цепочек над алфавитом [math]\Sigma[/math].

Определение:

Язык над алфавитом [math]\Sigma[/math] — некоторое подмножество [math]\Sigma^*[/math]. Иногда такие язык называют формальными, чтобы подчеркнуть отличие от языков в привычном смысле.

Отметим, что язык в [math]\Sigma[/math] не обязательно должен содержать цепочки, в которые входят все символы [math]\Sigma[/math]. Поэтому, если известно, что [math]L[/math] является языком над [math]\Sigma[/math], то можно утверждать, что [math]L[/math] — это язык над любым алфавитом, являющимся надмножеством [math]\Sigma[/math].

Определение:

Пусть [math]x, y \in \Sigma^*[/math]. Тогда [math]xy[/math] обозначает их конкатенацию, т.е. цепочку, в которой последовательно записаны цепочки x и y.

Свойства

• [math](\alpha\beta)\gamma=\alpha(\beta\gamma)[/math]
• [math]\exists \varepsilon : \alpha\varepsilon=\varepsilon\alpha=\alpha[/math]

Таким образом, мы получаем свободный моноид слов.