Алфавит, буквы, слова. Операции над словами. запись слов на бесконечной ленте

МАШИНЫ ТЬЮРИНГА

Алфавит –любое непустое конечное множество, элементы алфавита называются буквами. Словом длины n (n Î N) над алфавитом А называется отображение u: [1; n ]→ A.

Пример. Пусть А ={|; *}, n = 5, u (1) = |, u (2) = |, u (3) = *, u (4) = |, u (5) = *. Тогда u = ||*|*.

Пусть u и v – слова над алфавитом А длины n ₁ и n ₂ соответственно. Упорядоченной склейкой слов u и v называется слово uv длины n ₁ + n ₂, заданное следующим правилом:

Пример. Пусть А ={|; *}, u = ||*|*, v = **|. Тогда uv = ||*|***|, vu = ***|*.

Пусть А – алфавит и . Назовем Λ пустым символом, а - алфавитом с пустым символом.

Бесконечной записью конечного слова над алфавитом А в алфавите с пустым символом называется отображение , удовлетворяющее следующим условиям: существуют n ₁ < n ₂ (n ₁, n ₂ Î Z) такие, что:

1)

2)

Длиной слова называется величина n ₂ - n ₁ +1. f (n ₁) называется первой буквой слова, f (n ₁ +1) – второй буквой, …, f (n ₂) – последней (n ₂ - n ₁ +1)-й буквой.

Бесконечная запись конечного слова иначе называется записью слова на бесконечной ленте. Эта запись привязана к конкретному участку ленты

Пусть n Î Z. Сдвигом t_n называется отображение , заданное правилом .

Теорема 15.1. Множество сдвигов относительно операции композиции образует абелеву группу.

Пусть - алфавит с пустым символом. На множестве бесконечных записей конечных слов над А введем отношение ~ следующим образом:

u ~ v Û

Теорема 15.2. Отношение ~ является отношением эквивалентности.