Cтраница 4
Задание любого ( однозначного) алфавитного отображения ф однозначно определяет соответствующее ему каноническое множество событий. Обратное, вообще говоря, неверно и имеет место лишь для автоматных отображений. [46]
Линейные грамматики и соответствующие КС-языки играют важную роль в теории формальных языков. Во многом это связано с тем, что линейные грамматики адекватно моделируют автоматные отображения. При этом необходимо учитывать, что если автомат с выходом задает частичное отображение вида ВХОД - ВЫХОД, то соответствующая моделирующая линейная грамматика порождает слова вида ВХОД о ВЫХОД, где ВХОД и ВЫХОД - входное и выходное слово автомата, а верхний индекс R означает зеркальное отображение слова ВЫХОД. [47]
Сущность задачи минимизации частичных автоматов состоит в следующем: дан частичный автомат ( Мура или Мили) А, индуцирующий частичное автоматное отображение ф, определенное на некотором множестве М слов входного алфавита. Требуется построить частичный автомат ( Мура или соответственно Мили) В, который индуцирует частичное автоматное отображение, совпадающее на множестве М с отображением ф, и имеет наименьшее число внутренних состояний среди всех автоматов ( Мура или Мили), удовлетворяющих этому условию. [48]
Из доказательства предложения 2.1 вытекает существование единого конструктивного приема, позволяющего по любому автоматному отображению с конечной областью определения ( заданному на конечном множестве слов) строить индуцирующий это отображение конечный автомат Мили или Мура. Нашей же целью является разработка более общего конструктивного приема, позволяющего строить конечные автоматы Мили и Мура, индуцирующие заданное автоматное отображение не только для случая конечной области определения, авсякий раз, когда такие автоматы существуют. [49]
В предыдущем параграфе было сказано, что любое отображение можно свести к частичному алфавитному отображению. Однако не всякое алфавитное отображение является автоматным. Рассмотрим подробнее автоматные отображения и взаимосвязь между автоматным отображением и произвольным алфавитным отображением. [50]