Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Теорема 7. 1






    Множество функций, вычисляемых конечными автоматами, замкнуто относительно операции суперпозиции.

    Доказательство

    Пусть f: A * ® B * и g: B * ® C * - словарные функции, вычисляемые автоматами Â и Á из состояний и соответственно.

    Рассмотрим устройство, получаемое подключением выхода автомата Â к входу автомата Á, как это изображено на рис. 7.5


    Â Á

    C

     

    Рис. 7.5

    Это устройство называется суперпозицией автоматов Â и Á. Входным и выходным алфавитами автомата C являются множества A и C. Множество состояний автомата C состоит из всевозможных пар (, ), где - состояние Â, а - состояние Á. Работа автомата C в каждый момент времени связана с переработкой очередного входного символа a Î A из текущего состояния (, ), при котором сначала автомат Â перерабатывает a во входной символ автомата Á, который перерабатывает его в выходной символ, автомата C. Измененение состояния C состоит в изменении состояний Â и Á под действием входных символов автоматов Â и Á.

    Тогда C является автоматом, который вычисляет функцию g f из начального состояния (, ).






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.