База ответов ИНТУИТ

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

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

Пусть регулярное выражение b*(a+b)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

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

Варианты ответа
для этого языка существует только одно регулярное выражение
(b*+a)*
подходит и 1, и 2(Верный ответ)
(a +b)*
b*ab*
Похожие вопросы
Пусть регулярное выражение (ab)*a определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 0(10 +1)*?

С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

С2 = < {0,1}, {q, p, r, s }, q, F2={p, r}, Φ2>,

С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, r, s}, Φ3>,

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

Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 1 (01)*?

С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

С2 = < {0,1}, {q, p, r, s }, q, F2={p, s}, Φ2>,

С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, s}, Φ3>,

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

Какие из следующих трех автоматов С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}, состоит из всех слов, которые заканчиваются на 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
Пусть язык 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, 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) = ε ?