0
голосов
0
ответов
7 показов
Языки L_1, L_2, ..., L_2018 задаются регулярными выражениями
Языки L_1, L_2, ..., L_2018 задаются регулярными выражениями. Необходимо построить полиномиальный алгоритм, который бы проверял, что пересечение их вс ...
1
голос
0
ответов
57 показов
Эффективная система доказательств
Существует такое определение системы доказательств: пусть дан язык $%L$% над некоторым алфавитом $%\Sigma$%, тогда системой доказательств для языка $% ...
0
голосов
0
ответов
75 показов
Система регулярных уравнений
Пример:$$ X = \alpha X + \beta Y + \delta $$$$ Y = \gamma X + \mu Y + \epsilon $$Из первого:$$ X = a^{\ast} (\beta Y + \delta) $$подставляем во второе ...
0
голосов
0
ответов
57 показов
Проверка на задаваемость конечным преобразователем
Задаётся ли конечным преобразователем язык $%\{(x, y) | x > y \log_2 y\}$%, где $%x$% и $%y$% заданы в двоичной записи начиная с младших битов?Коне ...
0
голосов
0
ответов
47 показов
Как показать порождение КСГ для языка Дика?
Где Dyck_n \in (\Sigma ^ (n))* это язык правильных скобочных последовательностей n типовразличных скобок
0
голосов
0
ответов
110 показов
Привести грамматику к нормальной форме Хомского / Грейббах
3 Привести грамматику к нормальной форме Хомского4 Привести грамматику к нормальной форме ГрейббахS → AaA→ BbB→ CcC→ Dd|C→ eD→ ecbz| Ddcbz
0
голосов
0
ответов
57 показов
Построить детерминированный МП-автомат и КС грамматику распознающую язык, если это возможно
Построить детерминированный МП-автомат и КС грамматику распознающую язык, если это возможно: ∑ ={a,b}$$L = { a^{(n^3 + 1)}| n >= 1}$$
0
голосов
0
ответов
222 показа
Формальные системы. Определить множество формулой первого порядка или доказать, что это невозможно.
Формулы первого порядка с предикатными символами $%B(x), P(x, y)$% будем интерпретировать на непустых словах в алфавите $%\{0, 1\}$% так: переменные ф ...
0
голосов
0
ответов
104 показа
Регулярное выражение
Здравствуйте. Мне необходимо для регулярного языка построить регулярное выражение.У меня получилось вот это:$$ L=\left\{((a,b)^2 )^k\cdot ((b,c)^m )^2 ...
1
голос
0
ответов
73 показа
Доказать, что существует язык L, для которого не существует машины Тьюринга
Доказать, что существует язык L, для которого не существует машины Тьюринга, которая бы принимала на вход два слова, разделенных символом-разделителем ...
1
голос
1
ответ
80 показов
Докажите, что язык L={a^ib^j: i,j∈N, НОД(i,j)=1} является нерегулярным.
Докажите, что язык L={a^ib^j: i,j∈N, НОД(i,j)=1} является нерегулярным.
0
голосов
0
ответов
83 показа
Доказать, что если при прочтении двух слов x,y∈T∗ минимальным пДКА
Доказать, что если при прочтении двух слов x,y∈T∗ минимальным пДКА он оказывается в одном и том же состоянии ⇔ x L-эквивалентен y
0
голосов
0
ответов
86 показов
Доказать что КМП автомат Aw для любого слова w из T*
Доказать что КМП автомат Aw для любого слова w из T является минимальным полным ДКА для языка Tw (распознаёт все слова, оканчивающиеся на w)
0
голосов
0
ответов
78 показов
Доказательство размера выпуклой оболочки
Рассмотрим множество $%\mathbb{N} \times \mathbb{N}$% и различные его подмножества $% P \subset \mathbb{N} \times \mathbb{N}$%, такие что выпуклая обо ...
0
голосов
0
ответов
109 показов
НКА с двумя завершающимися состояниями
Достаточно ли в определении НКА(недетерминированный конечный автомат) с однобуквенными переходами двух завершающих состояний?
55 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.