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

L1 = { a²bⁿa² | n > 0 },

L2 = { ww | w = a²bⁿa² , n > 0 },

L3 = { wv | w = a²bⁿa² , v = b²a^mb² для произвольных n,m > 0 }.

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

L1 = { wbw | w = aⁿ , n > 0 },

L2 = { bwwb | w = aⁿ , n > 0 },

L3 = { (ab)ⁿa^m | n, m > 0 }.

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

L1 = { ww | w = b²aⁿb , n > 0 },

L2 = { b²aⁿb | n > 0 },

L3 = { (ab)ⁿaⁿb | n > 0 }.

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a →​ 1, 0 a →​ 2, 0 b →​ 0, 1 a →​ 2, 1 b →​ 1, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a →​ q1, q1 b →​ q0,q1 a →​ q2, q2 b →​ q1

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a →​ 1, 0 b →​ 3, 1 a →​ 2, 1 b →​ 1, 2 a →​ 1, 2 b →​ 3, 3 a →​ 3, 3b →​ 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 b →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2, q2 b →​ q0

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?

С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2},Φ₁> ,

С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2},Φ₂> ,

С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a →​ 1, 0 b →​ 3, 1 a →​ 3 1 b →​ 2, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a →​ q0, q0 b →​ q1, q1 a →​ q1, q1 a →​ q2

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

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

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

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

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

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