Главная
Каталог задач
Каталог заданий по Другое - Высшая математика
Детерминированные функции, ограниченно-детерминированные функции. Диаграммы Мура. Автоматы.

Тема Дискретная математика

04 Детерминированные функции, ограниченно-детерминированные функции. Диаграммы Мура. Автоматы.

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела дискретная математика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#59141

Для функции $y(t)$ с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ , заданной как:

( { 0 если x(1) = x(2) = ...= x(t) = 0 y(t) = ( 1, если среди x(1),x(2),...,x(t) вст ретилась хоть од на ед иница

найти её вес, нарисовать усечённое информационное дерево и построить диаграмму Мура.

Показать ответ и решение

1. Для того, чтобы найти вес нашей функции, сначала нарисуем её информационное дерево.

$PIC$

Теперь нам нужно понять, сколько в этом бесконечном информационном дереве неэквивалентных поддеревьев.

Ясно, что неэквивалентных поддеревьев будет всего 2. Это поддеревья вида

$PIC$

а также вида

$PIC$

Следовательно, вес нашей функции равен 2.

2. Для того, чтобы построить усечённое информационное дерево, мы должны сначала выбрать и пометить числами 0 и 1 две базовые вершины - корневую и любую другую так, чтобы помеченные разными номерами вершины задавали неэквивалентные деревья. И из каждой вершины выпустить $|A| = 2$ ребра. Получим такое усечённое дерево:

$PIC$

3. И, соответственно, диаграмма Мура получается, если мы в усечённом информационном дереве отождествим вершины с одинаковыми метками:

$PIC$

Ответ:

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#59143

Для функции $y(t)$ с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ , заданной как:

( { 0, если t = 1,2 y(t) = ( x(t− 2), если t > 2

найти её вес, нарисовать усечённое информационное дерево и построить диаграмму Мура.

Показать ответ и решение

Для функции $y(t)$ с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ , заданной как:

( { 0, если t = 1,2 y(t) = ( x(t− 2), если t > 2

найти её вес, нарисовать усечённое информационное дерево и построить диаграмму Мура.

Решение.

1. Для того, чтобы найти вес нашей функции, сначала нарисуем её информационное дерево.

$PIC$

Теперь нам нужно понять, сколько в этом бесконечном информационном дереве неэквивалентных поддеревьев.

Ясно, что неэквивалентных поддеревьев будет всего 4. Это поддеревья вида

$PIC$

Следовательно, вес нашей функции равен 4.

2. Для того, чтобы построить усечённое информационное дерево, мы должны сначала выбрать и пометить числами 0 и 1, 2 и 3 четыре базовые вершины - корневую и любые три другие так, чтобы помеченные разными номерами вершины задавали неэквивалентные деревья. И из каждой вершины выпустить $|A | = 2$ ребра. Получим такое усечённое дерево:

$PIC$

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#59144

Показать, что функция $y(t)$ с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ , заданная как:

( { 0 если t− нечётно y(t) = ( x(t2), если t− чётно

не является ограниченно-детерминированной.

Показать ответ и решение

Построим информационное дерево для нашей функции.

$PIC$

И дело в том, что это дерево содержит бесконечно много неэквивалентных поддеревьев.

Действительно, рассмотрим, например, функцию, задающуюся деревом, растущим из вершины на чётном ярусе 2 :

$PIC$

Тогда функция, заданная этим поддеревом, примет значение единица через 2 яруса (на 4 ярусе исходного дерева).

В то время как, например, если рассмотреть функцию, задающуюся деревом, растущим из следующей вершины на чётном ярусе 4:

$PIC$

Тогда функция, заданная этим поддеревом, примет значение единица только через 4 яруса (на 8 ярусе большого дерева) после помеченной вершины.

Таким образом, чем ниже мы возьмём вершину, тем дальше от неё функция, задаваемая такой вершиной, начнёт принимать значение 1.

То есть, если мы берём вершину на ярусе $t$ , то функция, определяемая деревом, растущим из этой вершины, начнёт принимать значение 1 начиная с яруса $2t$ исходного дерева - всякий раз всё дальше и дальше - таким образом, деревья, растущие из вершин на разных ярусах, не могут быть эквивалентны.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 4#59145

Показать, что функция $y(t)$ с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ , заданная как:

y(t) = x(1)⋅x(2) ⋅...⋅x(t+ 1) → x(1)

(где $→$ - это стрелка импликации, равная 1, если посылка ложна, либо заключение истинно, и равная 0 только тогда, когда посылка истинна, а заключение ложно)

хотя и формально в своей записи использует значение $x(t+ 1)$ , тем не менее, является детерминированной.

Показать ответ и решение

Формально, если вглядеться в определение функции, то её значение $y(t)$ в $t$ момент времени как будто бы зависит от подаваемого на вход в следующий момент времени $x(t+ 1)$ .

Однако давайте чуть пристальнее проанализируем поведение нашего выхода $y(t)$ .

$y(t)$ по определению равна 0, если одновременно посылка $x (1 )⋅x(2)⋅...⋅x (t + 1)$ истинна, а заключение $x(1)$ - ложно.

Но чтобы посылка была истинной, все $x(1),x (2 ),...,x(t+ 1)$ должны быть равны единице. Но в частности и $x(1)$ должен быть равен 1. Значит заключение $x(1)$ в таком случае уже не может быть ложным.

Следовательно, $y(t)$ вообще никак не может быть ложным. Получается, $y(t)$ в любой момент времени $t$ равна 1.

Таким образом наша функция детерминирована - она не зависит от $x(t+ 1)$ и, более того, она вообще не зависит от $x$ ни в какой момент времени - проанализировав мы поняли, что $y(t) ≡ 1$ $∀t = 1,2,...$ . А константная функция, разумеется, тоже детерминирована - её значение в любой момент времени можно вычислить, вообще ничего не зная про входные данные.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 5#59146

Привести пример недетерминированной функции с входным алфавитом $A = {0,1}$ и выходным алфавитом $B = {0,1}$ .

Показать ответ и решение

Например, можно взять такую функцию

( { 0 если x(t+ 5) = 0 y(t) = ( 1, если x(t+ 5) = 1

Таким образом, чтобы вычислить даже самое первое выходное значение $y(1)$ , нам нужно подождать, пока функции на вход подадут шестое значение $x(6)$ . По определению, такая функция не является детерминированной, потому что $y(1)$ должен зависеть только от $x(1)$ .

Ответ:

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел