Примеры отношения эквивалентности. Пример 1. Рассмотрим в качестве множества X множество натуральных чисел:

Пример 1. Рассмотрим в качестве множества X множество натуральных чисел: . Для него рассмотрим обычное равенство натуральных чисел. Скажем, что два натуральных числа эквивалентны, если они равны в обычном смысле. Очевидно, что это есть отношение эквивалентности.

Пример 2. Рассмотрим произвольное натуральное число . Числа x и y назовем эквивалентными , если они дают один и тот же остаток при делении на . Очевидно, что это есть отношение эквивалентности.

Пример 3. Введем отношение эквивалентности на множестве слов, длина которых не меньше числа . Рассмотрим множество этих слов в алфавите . Скажем, что пара слов и эквивалентны, если совпадают их первые букв. Убедитесь сами, что все три свойства эквивалентности выполнены.

Утверждение. Пусть – множество, – отношение эквивалентности на нем. Тогда разбивает все элементы на классы эквивалентных элементов (Любая пара различных классов не пересекается между собой- , и их объединение совпадает с множеством ; ; количество классов может быть бесконечным). Любая пара элементов одного класса эквивалентна, а любая пара элементов различных классов не эквивалентна. Данное разбиение однозначно определяется отношением эквивалентности .

Докажите это утверждение самостоятельно.

Пример 1. Классы эквивалентности – одноэлементные подмножества , ,...

Пример 2. Пусть задано отношение эквивалентности на множестве натуральных чисел . Числа эквивалентны, если их остатки от деления на совпадают. Классы эквивалентности – , .

Пример 3. Если для тех же натуральных чисел взять вместо двух произвольное число , то число классов эквивалентности будет так же . По одному классу на каждый из их остатков.

Определение. Пусть заданы конечные алфавиты: – входной и – выходной. Задана функция , которая ставит в соответствие бесконечной последовательности из алфавита некоторую бесконечную последовательность алфавита .
Функция называется детерминированной, если начало выходного слова однозначно определяется соответствующим началом входного слова, т.е. выполнено следующее формальное определение: для любых слов и , выполн имеющих одно начало их образы , будут иметь одно и тоже начало длины равной длине .
(любая пара слов , которые имеют одно и тоже начало преобразуются функцией в пару слов , которые имеют одно и тоже начало соответствующее началу ).
Говоря другими словами, начало длины выходного слова не зависит от конца входного слова (начиная с -ой буквы).

Определение. Остаточной функцией, соответствующей слову и детерминированной функции , называют функцию , которая определяется следующим образом. Чтобы определить значение этой функции на входной последовательности , добавим к этому слову приставку , получим слово , применим к этому слову функцию , в результате получим слово и тогда значением объявим слово .
; ;
; ; ;
.

Определение. Функция называется ограниченно-детерминированной, если число различных остаточных функций конечно.

Пример. Рассмотрим константно-периодическую функцию. Такая функция на любом входном слове равна одному и тому же выходному слову, и есть некоторое периодичное слово, бесконечное повторение некоторого конечного слова .
Очевидно, что такая функция детерминированная, а число различных остаточных функций равно длине периода, т.е. длине слова .

Замечание. Каждая остаточная функция является детерминированной.

Дадим эквивалентное определение ограниченно-детерминированных функций в классе некоторых устройств, которые их вычисляют.

Определение. Конечным автоматом называют набор из шести множеств , где – входной алфавит, – выходной алфавит, – множество состояний автомата (конечные множества), - начальное состояние автомата, – функция переходов состояний ; – функция выходов автомата .

Автомат имеет две ленты (входную и выходную) и считывающий элемент, который в каждый момент времени находится в одном из своих состояний . Функционирование автомата однозначно определяется функцией переходов, функцией выходов и входным словом, которое написано на входной ленте. В начальный момент времени состояние автомата и он обозревает самую левую букву входного слова. Далее процесс вычисления происходит следующим образом:
1. Если в текущий момент времени считывающий элемент находится в состоянии , обозревая символ на входной ленте, то он переходит в состояние согласно функции переходов на паре ; на выходной ленте считывающий элемент печатает символ согласно функции выхода и сдвигается на ячейку вправо. После считывания входного слова, т.е. в момент времени равного длине входного слова, на выходной ленте будет написано некоторое выходное слово в алфавите . Это слово и объявляем выходом автомата на входном слове, записанном на ленте. Таким образом, автомат вычисляет некоторую словарную функцию , которую называют функцией соответствующего автомата, .

Дата добавления: 2017-01-13