Конечные автоматы и преобразователи.

Распознователь состоит из 3 частей: входной ленты, устройства упр-ния (УУ) с конечной памятью и вспомогательной памятью.

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

2 функции во вспомогательной памяти: доступа к памяти и преобразование памяти.

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

Распознаватели: 1. Односторонние и двусторонние (головка движется и вправо и влево); 2. Без внешней памяти, с ограниченным кол-ом памяти и с неогранич кол-вом памяти; 3. Детерминированные (когда распознаватель из 1 конфигурации перейти в другую конфигурацию) и недетерминированные (из 1 конфигурации распознаватель может перейти во мн-во других конфигурацию).

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

Распознаватель работает по тактам. За один такт работы распознавательная головка может сдвигаться на 1 клетку влево (вправо) или остаться неподвижной.

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

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

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

Конечный автомат – простейший распознаватель, у кот отсутствует вспомогательная память.

Недетерминированные конечные автоматы (НКА) наз-ся пятерка объектов K=(Q, ), где Q – конечное мн-во сотстояний УУ, - конечный алфавит вход символов, - функция переходов, задается отображением -конечное мн-во подмножеств мн-ва Q, – нач состояние УУ, -мн-во заключительных состояний.

С помощью конечного автомата можно легко определить, принадлежит или нет заданная входная цепочка языку, допускаемому этим автоматом. Такт работы НКА опр-ся текущим состоянием УУ и текущ входным символом.

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

Детерминированный конечный автомат (ДКА) – КА вида: =(Q, ). Если мн-во содержит не более одного состояния для любого . Если мн-во для всех содержит 1 состояние, то автомат К наз-ся полностью определенным КА.