Алфавит, слова.

Основные понятия и определения.

Введем понятие ленты, разделенной на равные участки, называемые ячейками или клетками. Будем считать ленту конечной в любой данный момент, но неограниченно надстраиваемой в обе стороны, так, что у каждой ячейки есть соседние справа и слева. Одно из возможных состояний ячеек будем называть исходным. Ячейки, находящиеся в этом состоянии, будем называть пустыми.

Произвольное конечное множество букв назовем алфавитом. Конечная последовательность ячеек, занятых некоторыми буквами назовем словом. Длиной слова называется число занятых ячеек. Пусть А, В – слова, записанные в алфавите, не содержащем самих символов А и В. Тогда АВ – слово, получающееся, если сначала выписать слово А, а затем приписать справа слово В. Слово АВ называется композицией (или произведением) слов А и В. Удобно ввести еще пустое слово, композиция которого с любым словом считается по определению равной этому последнему слову. Пустое слово не следует путать с пустой ячейкой.

Слово А называется подсловом слова В, если В можно представить в виде , где С и D – некоторые (возможно пустые) слова. Слово А может входить несколько раз в слово В, при этом говорят о первом, втором и т.д. вхождении слова А в слово В.