игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Введение в схемы, автоматы и алгоритмы / Тест 6

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

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

Ответ:

 (1) все слова в алфавите {0, 1}, начинающиеся на 0101, с длиной > 7 

 (2) все слова четной длины в алфавите {0, 1}, начинающиеся на 0101 

 (3) все слова четной длины в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111 

 (4) все слова в алфавите {0, 1}, начинающиеся на 0101, в которых на четных местах стоят единицы и которые содержат подслово 1111 

 (5) ни одна из предыдущих 


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

Ответ:

 (1) все слова в алфавите {0, 1}, заканчивающиеся на 10, с длиной > 5 

 (2) все слова четной длины в алфавите {0, 1}, содержащие подслово 0000 

 (3) все слова четной длины в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули 

 (4) все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули и которые содержат подслово 0000 

 (5) все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на нечетных местах стоят нули и которые содержат подслово 0000 


Номер 3

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

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

Ответ:

 (1) все слова в алфавите {0, 1}, начинающиеся на 0, с длиной > 5 

 (2) все слова в алфавите {0, 1}, начинающиеся на 0 и содержащие подслово 1111, в которых единицы идут блоками четной длины 

 (3) все слова нечетной длины в алфавите {0, 1}, начинающиеся на 0 и содержащие подслово 1111, в которых на нечетных местах стоят нули 

 (4) все слова в алфавите {0, 1}, начинающиеся на 0, в которых на четных местах стоят нули и которые содержат подслово 1111 

 (5) все слова в алфавите {0, 1}, начинающиеся на 0, в которых единицы идут блоками четной длины 


Упражнение 2:
Номер 1

Пусть язык 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

Ответ:

 (1) только W1 

 (2) только W2 

 (3) только W3 

 (4) W1 и W2 

 (5) W1 и W3 

 (6) W2 и W3 

 (7) все 


Номер 2
Пусть язык 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

Ответ:

 (1) только W1 

 (2) только W2 

 (3) только W3 

 (4) W1 и W2 

 (5) W1 и W3 

 (6) W2 и W3 

 (7) все 


Номер 3
Пусть язык 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

Ответ:

 (1) только W1 

 (2) только W2 

 (3) только W3 

 (4) W1 и W2 

 (5) W1 и W3 

 (6) W2 и W3 

 (7) все 


Упражнение 3:
Номер 1

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

С1 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2, q3, q4, q5, q6, q7}, 0, F1={1,2}, Φ1>,

С2 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F2={ 1,2}, Φ2>,

С3 = < {0, 1}, {0, 1, 2, 3, q0, q1, q2 }, 0, F3={0,1,2}, Φ3>,

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1 и C2 

 (5) C1 и C3 

 (6) C2 и C3 

 (7) все 


Номер 2

Пусть задан ДКА 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) = ε Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

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

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

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

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1 и C2 

 (5) C1 и C3 

 (6) C2 и C3 

 (7) все 


Номер 3

Пусть задан ДКА 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) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

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

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

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

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1 и C2 

 (5) C1 и C3 

 (6) C2 и C3 

 (7) все 


Упражнение 4:
Номер 1

Пусть задан ДКА 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>,

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1и C2 

 (5) C1и C3 

 (6) C2и C3 

 (7) все 


Номер 2

Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {S}, ΦA > с программой ΦA: { Q a →​ R, Q b →​ P, P b →​ P, P a →​ R, R a →​ Q, R b →​ S, S a →​ R, S b →​ S} и гомоморфизм h: {0, 1, 2}* →​ {a, b}*: h(0) = bab, h(1) = aba, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

С1 = < {0, 1}, { Q, P, R, S }, 0, F1={S}, Φ1>,

С2 = < {0, 1}, { Q, R, S }, 0, F2={ S }, Φ2>,

С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ S }, Φ3>,

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1и C2 

 (5) C1и C3 

 (6) C2и C3 

 (7) все 


Номер 3
4. 

Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {P, S}, ΦA > с программой ΦA: { Q a →​ R, Q b →​ P, P b →​ S, P a →​ P, R a →​ R, R b →​ S, S a →​ S, S b →​ R} и гомоморфизм h: {0, 1, 2}* →​ {a, b}*: h(0) = bab, h(1) = aa, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

С1 = < {0, 1}, { Q, P, R, S }, 0, F1={P, S}, Φ1>,

С2 = < {0, 1}, { Q, S }, 0, F2={ S }, Φ2>,

С3 = < {0, 1}, { Q, R, S }, 0, F3={ S }, Φ3>,

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

files

Ответ:

 (1) только C1 

 (2) только C2 

 (3) только C3 

 (4) C1и C2 

 (5) C1и C3 

 (6) C2и C3 

 (7) все 


Упражнение 5:
Номер 1
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв a превосходит количество букв b не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Ответ:

 (1) cnaaab 

 (2) banbnaaa 

 (3) an+2bn 

 (4) can+2bnc 

 (5) cbncan+3b 


Номер 2
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Ответ:

 (1) cnbbbaaabb 

 (2) banbn+4aaa 

 (3) cbn+2 

 (4) bn+2canc 

 (5) bncanbbb 


Номер 3
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

Ответ:

 (1) bbbcnaabb 

 (2) bcbn+4anaca 

 (3) canbn+3c 

 (4) bn+2canc 

 (5) ancbn+3c 


Упражнение 6:
Номер 1

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

L1 = { a2bna2 | n > 0 },

L2 = { ww | w = a2bna2 , n > 0 },

L3 = { wv | w = a2bna2 , v = b2amb2 для произвольных n,m > 0 }.


Ответ:

 (1) только L1 

 (2) только L2 

 (3) только L3 

 (4) L1 и L2 

 (5) L1 и L3 

 (6) L3 и L2 

 (7) все 


Номер 2

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

L1 = { ww | w = b2anb , n > 0 },

L2 = { b2anb | n > 0 },

L3 = { (ab)nanb | n > 0 }.


Ответ:

 (1) только L1 

 (2) только L2 

 (3) только L3 

 (4) L1 и L2 

 (5) L1 и L3 

 (6) L3 и L2 

 (7) все 


Номер 3

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

L1 = { wbw | w = an , n > 0 },

L2 = { bwwb | w = an , n > 0 },

L3 = { (ab)nam | n, m > 0 }.


Ответ:

 (1) только L1 

 (2) только L2 

 (3) только L3 

 (4) L1 и L2 

 (5) L1 и L3 

 (6) L3 и L2 

 (7) все 




Главная / Алгоритмы и дискретные структуры / Введение в схемы, автоматы и алгоритмы / Тест 6