Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разраста
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
вопрос
Правильный ответ:
bbbcnaabb bcbn+4anaca canbn+3c bn+2canc ancbn+3c Сложность вопроса
49
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
спасибо за ответ
05 сен 2020
Аноним
Я сотрудник университета! Незамедлительно сотрите этот ваш сайт с ответами интуит. Это невозможно
12 май 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, ΦA> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, ΦB>, [Большая Картинка] распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует? C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, ΦC >, D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ΦD >, [Большая Картинка]
- # Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?
- # Пусть задан ДКА A =< {a, b, c}, {0, 1, 2, 3}, 0, F= {2}, ΦA > с программой ΦA: { 0 a → 1, 0 b → 1, 0 c → 0, 1 a → 1, 1 b → 2, 1 c → 2, 2 a → 3, 2 b → 3, 2 c → 2, 3 a → 3, 3 b → 3, 3 c → 3} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 11, h(c) = ε Какие из следующих трех автоматов С1 , С2, С3 распознают гомоморфный образ h(LA)? С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>, С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>, С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { ww | w = b2anb , n > 0 }, L2 = { b2anb | n > 0 }, L3 = { (ab)nanb | n > 0 }.
- # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?