Загрузка...

Глава 2. ОСНОВЫ ОБЩЕЙ ТЕОРИИ АВТОМАТОВ


«Многие вещи нам не понятны не потому,
что наши понятия слабы, но потому,
что сие вещи не входят в круг наших понятий»
К. Прутков.
ТЕМА 2.1. ЭФФЕКТИВНАЯ ПРОЦЕДУРА И АЛГОРИТМ
1. При доказательстве неразрешимостей для формальных грамматик мы предполагали, что выполнимы некоторые действия (операции) над конечными последовательностями строк конечной длины. Если получалось доказать, что существует конечная последовательность действий над конечным числом объектов, приводящая к решению поставленной задачи, то мы говорили о том, что существует эффективная процедура.
2. Выполнимость элементарных операций или их последовательности не обсуждалось, а предполагалось, что они изначально выполнимы, что не очевидно.
3. Эффективная процедура становится определенной, объективной, если задается алгоритмическая модель, то есть нечто внешнее по отношению к субъективным представлениям каждого человека, которое позволяет однозначно трактовать как элементарные операции, так и их последовательности конечной длины.

ТИПЫ АЛГОРИТМИЧЕСКИХ МОДЕЛЕЙ.

1. Машина Тьюринга.
2. Детерминированные устройства (автоматы).

В рамках формальных систем используются формальные системы, являющиеся алгоритмическими моделями.
1. Формальные языки и грамматики.
2. Ассоциативное исчисление.
Определение. АССОЦИАТИВНЫМ ИСЧИСЛЕНИЕМ или ПОЛУСИСТЕМОЙ ТУЭ называется формальная система , задаваемая парой объектов , где
— алфавит нетерминальных знаков, — множество ассоциаций (двунаправленных продукций).
Пример. , где множество ассоциаций .

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

ПРЕДСТАВИМОСТЬ ФОРМАЛЬНЫХ СИСТЕМ АВТОМАТАМИ.

Пусть задана формальная грамматика и некоторое устройство – автомат , относительно которого известно, что оно может находиться в одном из конечного множества состояний в каждый момент времени, где выделяется два состояния:
— конечное или заключительное состояние,
— начальное состояние.
На вход автомата подается произвольная строка в алфавите (с выхода снимается произвольная строка в алфавите, совпадающем с алфавитом грамматики ).

Определение. Автомат называется АВТОМАТОМ АКЦЕПТОРОМ (РАСПОЗНАВАТЕЛЕМ), если произвольная строка языка , будучи поданная на вход автомата переводит его из начального состояния в заключительное за конечное время и не переводит его в заключительное состояние, если строка не принадлежит языку . Такой автомат будем называть АВТОМАТОМ – РАСПОЗНАВАТЕЛЕМ.

Определение. Автомат называется ПОРОЖДАЮЩИМ АВТОМАТОМ для языка , если при изменении его состояния из состояния в состояние на выходе автомата появляется строка языка , порожденная грамматикой .

Определение. АВТОМАТОМ – ПРЕОБРАЗОВАТЕЛЕМ называется автомат, который для каждой распознанной строки языка на выходе порождает некоторую строку , принадлежащую языку , где — некоторые формальные грамматики.

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

ПРЕДВАРИТЕЛЬНАЯ КЛАССИФИКАЦИЯ АВТОМАТОВ.

Грамматика Алгоритмическая модель (автомат)
Типа 0 (произвольная грамматика). Адекватная машина Тьюринга.
Типа 1 (контекстная грамматика). Двухстековый (магазинный) автомат.
Типа 2 (контекстно-свободная грамматика). Одностековый ( магазинный) автомат.
Типа 3 (регулярная грамматика). Конечный автомат.

Автомат представляет грамматику заданного типа если он способен распознать и породить строки, задаваемые этой грамматикой.

Загрузка...