Введение в схемы, автоматы и алгоритмы - тест 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) = ε ?

Ответ:

---

Номер 2

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

Ответ:

---

Номер 3

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

Ответ:

---

Упражнение 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

Ответ:

---

Номер 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

Ответ:

---

Номер 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

Ответ:

---

Упражнение 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>,
 
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

---

Номер 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>, 
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

---

Номер 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>, 
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

---

Упражнение 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>, 
где программы заданы в следующих таблицах.
 

Ответ:

---

Номер 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>, 
где программы заданы в следующих таблицах.
 

Ответ:

---

Номер 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>, 
где программы заданы в следующих таблицах.

Ответ:

---

Упражнение 5:

---

Номер 1

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

Ответ:

---

Номер 2

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

Ответ:

---

Номер 3

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

Ответ:

---

Упражнение 6:

---

Номер 1

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { a2bna2 | n > 0 },
L2 = { ww | w = a2bna2 , n > 0 },
L3 = { wv | w = a2bna2 , v = b2amb2 для произвольных n,m > 0 }.

Ответ:

---

Номер 2

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { ww | w = b2anb , n > 0 },
L2 = { b2anb | n > 0 },
L3 = { (ab)nanb | n > 0 }.

Ответ:

---

Номер 3

Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.
L1 = { wbw | w = an , n > 0 },
L2 = { bwwb | w = an , n > 0 },
L3 = { (ab)nam | n, m > 0 }.

Ответ:

---