Главная /
Введение в схемы, автоматы и алгоритмы /
Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?
Какой язык L
является конкатенацией двух языков:
L1= {ε, b, ab, ba}
и L2= {ε, a, b, ba}
?
вопрос
Правильный ответ:
L = {ε, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}
L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}
L = {ε, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}
L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}
L = {ε, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}
Сложность вопроса
95
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Зачёт прошёл. Лечу пить отмечать халяву с тестами интуит
01 ноя 2017
Аноним
Какой студент находит эти ответы inuit? Это же очень просты вопросы
17 авг 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?
- # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые заканчиваются на bcc и содержат подслово aca Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 00, h(b) = 10, h(c) = ε ?
- # Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, ΦA > с программой ΦA: { Q a → P, Q b → Q, P b → P, P a → R, R a → Q, R b → S, S a → S, S b → S} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = aba, h(1) = aa, h(2) = ε Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)? С1 = < {0, 1}, { Q, P, R, S }, 0, F1={ R }, Φ1>, С2 = < {0, 1}, { Q, P, R, S }, 0, F2={ R }, Φ2>, С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ R }, Φ3>, где программы заданы в следующих таблицах. [Большая Картинка]
- # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x 1/2]? [Большая Картинка]
- # Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4) M1 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22 M2 = Зам(∧, *); Зам(∧,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22 M3 = if Нуль11 then Пуст else Коп* Зам(∧, *); Зам(∧,|); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Умн); Зам(#, *)) enddo; Выб33 endif. M4 = if Нуль11 then Пуст else Коп* Зам(∧, *); while Нуль13 do par*( Выч1, Коп#, Пуст); par# (Пуст, Сум); Зам(#, *)) enddo; Выб33 endif. построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Нульin - выдает 1, если i-ый аргумент из n аргументов равен ∧ (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),Выч1 – вычитает единицу в унарной системе: |j ⇐ |j-1 (| ⇐ ∧, ∧ ⇐ ∧) Какая из этих машин вычисляет функцию f(x) = xx в унарном кодировании, т.е. переводит вход |x в выход |y, где y = xx (пусть f(0)=0) ?