Главная страница
Финансы
Экономика
Биология
Ветеринария
Сельское хозяйство
Медицина
Математика
Начальные классы
Информатика
Вычислительная техника
Право
Юриспруденция
История
Философия
Логика
Этика
Религия
Политология
Социология
Физика
Промышленность
Энергетика
Языки
Языкознание
Культура
Искусство
Автоматика
Связь
Электротехника
Химия
Воспитательная работа
Другое
Дошкольное образование
Экология
Строительство
Русский язык и литература
Классному руководителю
Геология
Физкультура
Доп
образование
Иностранные языки
География
Логопедия
Школьному психологу
Технология
ИЗО, МХК
Обществознание
Казахский язык и лит
Механика
ОБЖ
Музыка
Директору, завучу
Социальному педагогу
Психология

автомат отобр-ие. 3 автоматные отображения и события


Название3 автоматные отображения и события
Анкоравтомат отобр-ие.doc
Дата02.12.2017
Размер46 Kb.
Формат файлаdoc
Имя файлаавтомат отобр-ие.doc
ТипДокументы
#25280

3.2.1. автоматные отображения и события


 

Отображения,            индуцируемые           абстрактными            автоматами,   будем  называть

автоматными отображениями.

Всякое автоматное отображение удовлетворяет следующим четырем условиям:

1. Автоматное отображение осуществляет однозначное отображение (как пра- вило, частичное) множества слов в некотором конечном алфавите Х (входное алфа- витное отображение) в множества слов в некотором конечном алфавите Y (выходное алфавитное отображение).

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

3. Автоматное отображение ϕ сохраняет длину слова. Любое слово p входного алфавита  на котором отображение ϕ определено, имеет ту же длину, что и его образ

ϕ (p). В частности, пустое слово переводится отображением ϕ в пустое слово.

4. Автоматное отображение ϕ переводит любой начальный отрезок слова р, на котором оно определено, в соответствующий (имеющий ту же длину) начальный от- резок слова ϕ (p).

Перечисленные условия называются условиями автоматности отображения.

Все слова входного алфавита разбиваются автоматным отображением на два класса: на класс допустимых и класс запрещенных слов. Совокупность всех запре- щенных слов для данного автоматного отображения  будет называться его областью запрета.

(аj, xi) не оп- ределена в противном слу (аj, xi)  равняется слову аj  xi   (получающемуся в результате при- писывания буквы xi к слову аj), если  слово аj xi содержится в А, и что   (а, x) этого автомата следующим образом: если аj – любое слово  из А, а xi – произвольная буква входного алфавита, то будем считать, что Рассмотрим произвольное (частичное) отображение ϕ, для которого выполня- ются сформулированные выше условия. Построим абстрактный (частичный) автомат Мура U, состояниями которого будут служить всевозможные  допустимые для ото- бражения ϕ слова входного алфавита Х = (х1, …, хn). Обозначим множество всех та- ких слов через А и определим функцию переходов  чае.

 

 

(a) остается неопределенной.(аi) равным последней букве слова ϕ(аi ); на пустом слове функция (а) автомата Мура U следую- щим образом: для любого непустого слова аi из А полагаем Выбирая в качестве выходного алфавита автомата U выходной алфавит ото- бражения ϕ,  построим сдвинутую функцию выходов

  и получа-В качестве начального состояния автомата выбираем пустое слово

  xi1 = xi1, xi2,…, xik.ем  автомат  Мура,  индуцирующий  исходное  отображение  ϕ. В  самом деле, пусть, q = xi1, xi2, …, xik  – любое допустимое слово отображения ϕ. Тогда все его начальные отрезки будут также допустимыми словами (в силу условия 2). После подачи на вход построенного автомата слова q, будет осуществляться последовательный его перевод в состояние 

При  этом  автомат  выдает  некоторую  последовательность  выходных букв

yj1, yj2, …, yjk  = p. Из способа определения данного автомата следует, что последняя буква  слова  р  совпадает  с  последней  буквой  слова  ϕ(q),  предпоследняя   буква слова     р – с последней буквой слова  ϕ(xi1, xi2, …, xik-1), которая в силу условия 4, совпадает с предпоследней буквой слова ϕ(q) и т. д. Продолжая сравнение и исполь- зуя условия 3, можно установить совпадение всех букв слова р с соответствующими им буквами слова ϕ(q). Следовательно, построенный автомат Мура U индуцирует ис- ходное (частичное) отображение ϕ.

Поскольку   можно интерпретировать автомат Мура U   как автомат Мили, то очевидно следующее предложение.

Если алфавитное отображение ϕ удовлетворяет сформулированным выше  че- тырем условиям автоматности, то можно построить автоматы Мили и Мура (как пра- вило, бесконечные), индуцирующие это отображение. В случае, когда область опре- деления отображение ϕ конечна, эти автоматы также можно считать конечными.

Данное предложение позволяет      применять термины «автоматное отображе-

ние» по всему алфавитному отображению, удовлетворяющему условиям автоматности.

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

Ранее   рассматривалась возможность интерпретации автомата Мура как авто-

мат Мили с тем же самым числом состояний. Рассмотрим теорему:

Для всякого конечного автомата Мили существует эквивалентный ему (инду- цирующий то же  самое отображение) конечный автомат Мура. Существует еди- ный конструктивный   прием (универсальный алгоритм  преобразования автоматов Мили в автоматы Мура), позволяющий по произвольному конечному автомату Мили, имеющему m входных сигналов и n состояний, построить эквивалентный ему авто- мат Мура, имеющий не более m⋅n + 1 состояний.

Условия автоматности накладывают весьма жесткие ограничения на класс ото-

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

Рассмотрим этот прием.

 

 

Пусть ϕ – произвольное (как правило, частичное) отображение множества слов в (конечном) алфавите Х в множество слов в (конечном) алфавите Y. Обозначим че- рез Р область определения этого отображения. Будем применять к отображению ϕ две операции.

Первая операция – выравнивания длин слов (операция выравнивания).

. и Ее суть: во входной и выходной алфавиты отображения ϕ (т. е. Х и Y) добавляется по одной новой букве, которые будем называть пустыми и обозначать через

так, чтобы длины полу- ченных в результате приписывания новых букв словам  р1 и q1 совпали., а к его об- разу  q = ϕ(p) приписывается  слева  nq  экземпляров букв Каждому слову р из Р приписывается справа mp экземпляров букв

Далее строится новое отображение ϕ1 некоторого множества Р1, слов в алфави-

), которое переводит друг в друга слова) в множества  слов в алфавите Y U (те Х U(

р1 и q1, полученные в результате выравнивания длин слов р и q соответственно: ϕ1(р1)

= q1 (р – пробегает при этом все множество P). Условимся считать, что отображение

ϕ1, получается из отображения ϕ с помощью операции выравнивания. Существует не-

которая стандартная операция выравнивания, при которой отображение ϕ1, однознач-

. Суть и но определяется отображением ϕ и присоединенными пустыми буквами

, приписываемых слева к слову q, принимается равным длине слова р., приписываемых справа к произвольному слову р из области определения отображения ϕ, принимается равным длине слова q = ϕ(p), а число nq пустых букв ее в том, что число mp пустых букв

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

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

В результате применения операции пополнения  к произвольному выровнен-

ному алфавитному отображению ϕ возникает новое отображение ϕ1  область опреде- ления которого удовлетворяет условию полноты. Условимся  называть это отображе- ние пополнением отображения ϕ.

Если пополнение ϕ1  отображения ϕ является однозначным, то очевидно,  что оно удовлетворяет  всем четырем условиям автоматности.
4.2 Содержание дисциплины

Тема 1.

Определение и классификация дискретных преобразователей информации. лабораторная работа (4 часа(ов)): Тема Определение и классификация дискретных преобразователей информации. Задача исследования дискретных преобразователей информации: непрерывный и дискретный подходы. Алфавитный способ кодирования информации. Классификация различных типов преобразователей. Определение различных типов преобразователей информации (конечные автоматы, вероятностные автоматы, автоматы с магазинной памятью, машины Тьюринга, машины с неограниченными регистрами ) Гомоморфизм и эквивалентность дискретных преобразователей.

Тема 2.

Автоматные операторы. лабораторная работа (4 часа(ов)): Автоматные операторы. Определение автоматного оператора. Необходимые и достаточные условия автоматности оператора. Теорема Рени. Терема о сведении произвольного словарного отображения к автоматном

Тема 3.

Эквивалентность дискретных преобразователей. лабораторная работа (6 часа(ов)): Эквивалентность. Эквивалентность автоматов типа Мили и Мура. Теорема о существовании минимального автомата в классе всех эквивалентных конечных автоматов. Разрешимость проблемы определения эквивалентных состояний в конечном автомате. Разрешимость проблемы определения эквивалентности для конечных автоматов.

Тема 4.

Задача распознавания языков. лабораторная работа (8 часа(ов)): Задача распознавания языков. Понятие языка. Теоретико-множественные свойства языков. Сравнительный анализ представления языков в детерминированных и вероятностных автоматах. Представимость языков в МП автоматах множеством состояний и опустошением магазина. Отношение левой взаимозамещаемости и его свойства. Теорема Майхилла-Нероуда. Теорема детерминизации источника.

Тема 5.

Регулярные языки и регулярные выражения. лабораторная работа (6 часа(ов)): Регулярные языки и регулярные выражения. Алгебра языков. Тождественные отношения в алгебре. Регулярные языки и регулярные выражения. Лемма о накачке. Теорема Клини (анализ и синтез).

Тема 6.

Грамматики. Понятие вывода в грамматиках. Иерархия Хомского. лабораторная работа (6 часа(ов)):

Грамматики. Понятие вывода в грамматиках. Иерархия Хомского. Праволинейные грамматики. Теорема о совпадении классов праволинейных и регулярных языков. КС-грамматики и КС-языки. Теорема о совпадении классов МП и КС языков. Лемма Огдена и ее следствия. Сравнение возможности МП и ДМП автоматов в распознавании языков.

Тема 7.

Тема Некоторые разрешимые и неразрешимые задачи в теории автоматов и грамматик. лабораторная работа (2 часа(ов)): Некоторые разрешимые и неразрешимые задачи в теории автоматов и грамматик. Задача принадлежности слова языку, задача определения пустоты языка, задача эквивалентности различных описания языков
написать администратору сайта