0
голосов
0
ответов
41 показ

Задача 1:С помощью алгоритма минимизации ДКА докажите, что ДКА КМП A_{w} для любого слова w ∈ T^{∗} является минимальным полным ДКА для языка Suff(w) ...
1
голос
1
ответ
106 показов

Опишите классы Майхилла-Нероуда для языка L={w|w=w^R} над алфавитом T={a,b}.Примечание: необходимо указать множества, на которые разбивается T^*, пока ...
0
голосов
0
ответов
147 показов

Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последователь ...
0
голосов
0
ответов
77 показов

Докажите рекурсивную перечислимость следующего множества:$$A = \{x |\ \varphi_x\ \text{принимает хотя бы одно значение, являющееся степенью числа 2}\} ...
0
голосов
0
ответов
86 показов

Пусть B ⊆ N × N есть рекурсивное множество пар натуральных чисел. Докажите, что мно-жество A, состоящее из всех таких z ∈ N, что точка (z, z) лежит в ...
0
голосов
0
ответов
62 показа

Пусть множество A ⊆ N рекурсивно, а f : N → N тотальная строго возрастающая вычислимаяфункция, т. е. f(x) < f(y) для всех x < y. Верно ли, что м ...
0
голосов
0
ответов
99 показов

Докажите, что множество$$A = \{ x \mid W_{x} \text{ либо пусто, либо одноэлементно}\},$$не является рекурсивно перечислимым. Здесь$$W_{x} = \{y \mid \ ...
0
голосов
0
ответов
61 показ

Докажите рекурсивную перечислимость следующего множества$$A = \{ x \mid \varphi_x \text{ принимает значение 2021 хотя бы в двух различных точках. } \} ...
0
голосов
0
ответов
86 показов

Пусть f : N → \N тотальная вычислимая функция. Верно ли, что множество всех натуральныхчисел x таких, что f(y) < f(x) для некоторого y > x, явля ...
0
голосов
0
ответов
89 показов

Пусть всюду определенная функция f : N → N строго возрастает, т. е. f(x) < f(y) для всех x < y,а множество N \ rng(f) конечно (здесь rng(f) есть ...
0
голосов
0
ответов
145 показов

Задача такая: Доказать, что функция f(x)=[log2(x)] примитивно рекурсивная ([ ] - целая часть). Важно доказать это БЕЗ использования ограниченного "мю" ...
-1
голосов
1
ответ
210 показов

Задача доказать, что функция рекурсивно-примитивная [log2(x)] - целая часть от логарифмапо условию сначала доопределяем f(0) = [log2(x)]=0далее f(x+1) ...
0
голосов
0
ответов
90 показов

Загадано k-элементное подмножество K n-элементного множества N.За один шаг можно спросить, лежит ли некоторое подмножество G множества N полностью вну ...
0
голосов
0
ответов
80 показов

Оцените трудоемкость рекурсивного алгоритма, разбивающего исходную задачу размераn на n задач размеров n/2 каждая, используя для этого n операций.1. М ...
0
голосов
0
ответов
75 показов

Докажите, что любую программу, которая использует неограниченную оперативную память, можно реализовать на ограниченном компьютере,который использует к ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru