Главная /
Введение в схемы, автоматы и алгоритмы /
Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?
Пусть S={aaa, aba, baa, bba}
Какая из следующих фраз описывает итерацию S*
этого языка?
вопрос
Правильный ответ:
все слова над
{a, b}
, длина которых делится на 3 и каждая третья буква есть a
, и слово длины 0
все слова в алфавите
{a, b}
длины не меньше 3, которые заканчиваются на a,
и пустое слово
все слова над
{a, b},
длина которых делится на 3 и которые заканчиваются на a
все слова четной длины, состоящие из символов
{a, b}
, которые заканчиваются на a
все слова длины не меньше 12, состоящие из символов
{a, b}
Сложность вопроса
95
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт всё. Мчусь отмечать отмечать 5 за тест интуит
14 ноя 2019
Аноним
Какой человек ищет данные тесты интуит? Это же безумно легко
27 июн 2016
Аноним
Благодарю за подсказками по интуит.
25 фев 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)} ( для каждого ребра третий параметр после ; - его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
- # Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- # Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением (00 + 1)*1? С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1> , С2 = < {0,1}, {q, p, r, s }, q, F2={ s}, Φ2> , С3 = < {0,1}, {q, p, r, s, t}, q, F3={ s}, Φ3> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b an (n ≥ 0 )?