Ограниченно- детерминированные функции и автоматные языки. Эквивалентность

Утверждение. Каждая функция, которую реализует автомат, является ограниченно-детерминированной, и для любой ограниченно-детерминированной функции существует автомат её вычисляющий.

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

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

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

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

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

Рассмотрим ограниченно-детерминированную функцию и построим по ней автомат, который ее вычисляет. Рассмотрим все различные остаточные функции которые соотвествуют конечным словам . Считаем, что – пустое слово, а соответствующая ему остаточная функция есть функция .

На множестве всех конечных слов введем отношение эквивалентности. Пару слов и объявим эквивалентными тогда и только тогда, когда соответствующие остаточные функции и равны. Нетрудно проверить, что данное определение действительно дает отношение эквивалентности на множестве конечных слов.

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

Каждому слову поставим в соответствие состояние автомата, которое обозначим также символами .

Функцию переходов и функцию выходов автомата в состоянии построим по следующему правилу. К слову добавляем букву входного алфавита , в результате получим слово . Применяя ограниченно-детерминированную функцию, получаем , где – слово, а – буква выходного алфавита. Для слова находим эквивалентного представителя среди . Тогда из вершины направляем ориентированное ребро в вершину и помечаем это ребро парой букв . Данное построение совершаем для всех представителей и всех входных букв .

Начальным состоянием автомата объявляем (пустое слово).

В результате получаем всюду определенный и однозначный автомат.

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

Для этого достаточно доказать следующее утверждение.

Утверждение. Входное слово эквивалентно выбранному представителю тогда и только тогда, когда слова и в графе построенного автомата ведут в одно и то же состояние .

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