.04 Детерминированные функции, ограниченно-детерминированные функции. Диаграммы Мура. Автоматы.
Ошибка.
Попробуйте повторить позже
Для функции 
с входным алфавитом 
и выходным алфавитом 
, заданной
как:
найти её вес, нарисовать усечённое информационное дерево и построить диаграмму Мура.
1. Для того, чтобы найти вес нашей функции, сначала нарисуем её информационное дерево.
Теперь нам нужно понять, сколько в этом бесконечном информационном дереве неэквивалентных
поддеревьев.
Ясно, что неэквивалентных поддеревьев будет всего 2. Это поддеревья вида
а также вида
Следовательно, вес нашей функции равен 2.
2. Для того, чтобы построить усечённое информационное дерево, мы должны сначала выбрать и
пометить числами 0 и 1 две базовые вершины - корневую и любую другую так, чтобы помеченные
разными номерами вершины задавали неэквивалентные деревья. И из каждой вершины выпустить
ребра. Получим такое усечённое дерево:
3. И, соответственно, диаграмма Мура получается, если мы в усечённом информационном дереве отождествим вершины с одинаковыми метками:
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
