Языки L_1, L_2, ..., L_2018 задаются регулярными выражениями. Необходимо построить полиномиальный алгоритм, который бы проверял, что пересечение их вс ...
Существует такое определение системы доказательств: пусть дан язык $%L$% над некоторым алфавитом $%\Sigma$%, тогда системой доказательств для языка $% ...
Пример:$$ X = \alpha X + \beta Y + \delta $$$$ Y = \gamma X + \mu Y + \epsilon $$Из первого:$$ X = a^{\ast} (\beta Y + \delta) $$подставляем во второе ...
Задаётся ли конечным преобразователем язык $%\{(x, y) | x > y \log_2 y\}$%, где $%x$% и $%y$% заданы в двоичной записи начиная с младших битов?Коне ...
Формулы первого порядка с предикатными символами $%B(x), P(x, y)$% будем интерпретировать на непустых словах в алфавите $%\{0, 1\}$% так: переменные ф ...
Здравствуйте. Мне необходимо для регулярного языка построить регулярное выражение.У меня получилось вот это:$$ L=\left\{((a,b)^2 )^k\cdot ((b,c)^m )^2 ...
Доказать, что существует язык L, для которого не существует машины Тьюринга, которая бы принимала на вход два слова, разделенных символом-разделителем ...
Рассмотрим множество $%\mathbb{N} \times \mathbb{N}$% и различные его подмножества $% P \subset \mathbb{N} \times \mathbb{N}$%, такие что выпуклая обо ...