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

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

Алфавит –любое непустое конечное множество, элементы алфавита называются буквами. Словом длины 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. Отношение ~ является отношением эквивалентности.