double arrow

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


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

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

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

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

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

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

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

1)

2)

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

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

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

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




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

u ~ v Û

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







Сейчас читают про: