Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?

(Отметьте один правильный вариант ответа.)

Варианты ответа

все слова нечетной длины, состоящие из символов {a, b}

все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

все слова над {a, b} , длина которых делится на 2, включая слово длины 0(Верный ответ)

все слова в алфавите {a, b} длины не меньше 2 и пустое слово

Ответ 4. Все слова длины не меньше 8, состоящие из символов {a, b}

Похожие вопросы

Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?

Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?

Пусть язык 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}, состоит из всех слов, которые начинаются на cac и содержат подслово bcb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где

h(a) = 0, h(b) = 11, h(c) = ε ?

Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые заканчиваются на bcc и содержат подслово aca Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* → {0, 1}* где h(a) = 00, h(b) = 10, h(c) = ε ?

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на abb и содержат число символов b кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = bab, h(1) = b, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?W1 = 210102012, W2 = 201000201021, W3 = 021010212

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые начинаются на aa и содержат число символов a кратное 3, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = aaa, h(1) = ba, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?

W1 = 21112, W2 = 20101012, W3 = 00211011

Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на aa и содержат число символов b кратное 4, и пусть гоморфизм h: {0, 1,2}* → {a, b}* задан равенствами: h(0) = bab, h(1) = a, h(2) = ε Какие из следующих трех слов принадлежат прообразу h^-1(L) языка L при гомоморфизме h?W1 = 211100112, W2 = 201010121, W3 = 0021010211

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, Φ_A > с программой Φ_A: { 0 a → 1, 0 b → 0, 0 c → 1, 1 a → 2, 1 b → 1, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 01, h(b) = 1, h(c) = εКакие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный образ h(L_A)?

С₁ = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F₁={2}, Φ₁>,

С₂ = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F₂={2}, Φ₂>,

С₃ = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F₃={2, (1,2)}, Φ₃>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, Φ_A > с программой Φ_A: { 0 a → 0, 0 b → 1, 0 c → 1, 1 a → 1, 1 b → 2, 1 c → 1, 2 a → 2, 2 b → 2, 2 c → 1} и гомоморфизм h: {a, b, c}* → {0, 1}*: h(a) = 1, h(b) = 01, h(c) = ε. Какие из следующих трех автоматов С₁, С₂, С₃ распознают гомоморфный образ h(L_A)?

С₁ = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F₁={2}, Φ₁>,

С₂ = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F₂={2}, Φ₂>,

С₃ = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F₃={2, (1,2)}, Φ₃>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).