Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?
Пусть язык L
в алфавите {a, b, c}
, состоит из всех слов, которые начинаются на aa
и содержат подслово bb
Какая из следующих фраз определяет язык h(L)
, являющийся образом L
при гомоморфизме h: {a, b, c}* → {0, 1}*
где h(a) = 01
, h(b) = 11
, h(c) = ε
?
вопрос
Правильный ответ:
все слова в алфавите
{0, 1}
, начинающиеся на 0101,
с длиной > 7
все слова четной длины в алфавите
{0, 1}
, начинающиеся на 0101
все слова четной длины в алфавите
{0, 1}
, начинающиеся на 0101
, в которых на четных местах стоят единицы и которые содержат подслово 1111
все слова в алфавите
{0, 1}
, начинающиеся на 0101
, в которых на четных местах стоят единицы и которые содержат подслово 1111
ни одна из предыдущих
Сложность вопроса
76
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Это очень простецкий вопрос intuit.
14 окт 2019
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x +1,(b) пока x < y делай P все,(c) пока x = y делай P все. .
- # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
- # Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где [Большая Картинка] Какие из следующих трех слов распознаются автоматом A? W= aaabbabab, V= babbbabba, U= ababaaab
- # На следующем рисунке представлены диаграммы двух конечных автоматов 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 >, [Большая Картинка]
- # Пусть c2(x, y) = 2x(2y+1) -1 - это функция нумерации пар, а c21(z) и c22(z) - это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и yРассмотрим функцию F(x), заданную равенствами: F(0) = 1, F(1) = 1, F(y+2) = F(y) + F(y+1) . Положим G(y) = c2(F(y), F(y+1))Так как F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G