ВУЗ:
Составители:
36
3.2. Представление событий в автоматах
Рассмотрим задачи, возникающие на этапе абстрактного анализа и синтеза ав-
томатов. Рассмотрим условия, при которых можно индуцировать любое алфавитное
отображение в автоматное.
Условия автоматности накладывают жесткие ограничения на класс отображе-
ний, которые могут быть индуцированы абстрактными автоматами. Большинство ал-
фавитных отображений, с которыми приходится иметь дело на практике, не удовле-
творяют этим условиям. Существует, однако, стандартный прием, позволяющий ин-
дуцировать любое алфавитное отображение в автоматное. К описанию этого приема
мы и переходим.
3.2.1. Автоматные отображения и события
Отображения, индуцируемые абстрактными автоматами, будем называть
автоматными отображениями.
Всякое автоматное отображение удовлетворяет следующим четырем условиям:
1. Автоматное отображение осуществляет однозначное отображение (как пра-
вило, частичное) множества слов в некотором конечном алфавите Х (входное алфа-
витное отображение) в множества слов в некотором конечном алфавите Y (выходное
алфавитное отображение).
2. Область определения автоматного отображения удовлетворяет условию пол-
ноты, т. е. вместе с любым содержащимся в ней словом также содержатся все началь-
ные отрезки этого слова. Пустое слово всегда входит в область определения отобра-
жения.
3. Автоматное отображение ϕ сохраняет длину слова. Любое слово p входного
алфавита на котором отображение ϕ определено, имеет ту же длину, что и его образ
ϕ (p). В частности, пустое слово переводится отображением ϕ в пустое слово.
4. Автоматное отображение ϕ переводит любой начальный отрезок слова р, на
котором оно определено, в соответствующий (имеющий ту же длину) начальный от-
резок слова ϕ (p).
Перечисленные условия называются условиями автоматности отображения.
Все слова входного алфавита разбиваются автоматным отображением на два
класса: на класс допустимых и класс запрещенных слов. Совокупность всех запре-
щенных слов для данного автоматного отображения будет называться его областью
запрета.
Рассмотрим произвольное (частичное) отображение ϕ, для которого выполня-
ются сформулированные выше условия. Построим абстрактный (частичный) автомат
Мура U, состояниями которого будут служить всевозможные допустимые для ото-
бражения ϕ слова входного алфавита Х = (х
1
, …, х
n
). Обозначим множество всех та-
ких слов через А и определим функцию переходов δ (а, x) этого автомата следующим
образом: если а
j
– любое слово из А, а x
i
– произвольная буква входного алфавита, то
будем считать, что δ (а
j
, x
i
) равняется слову а
j
x
i
(получающемуся в результате при-
писывания буквы x
i
к слову а
j
), если слово а
j
x
i
содержится в А, и что δ (а
j
, x
i
) не оп-
ределена в противном случае.
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
