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

Правильный ответ:

• # Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(∧), f(¬),g(¬),h(∧), i(∧), k(¬), m(∨) } (после имени вершины в скобках указана ее метка - переменная или булева функция), E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m? P1: P2: P3: V = X ∧ V; f = ¬Y; Y = ¬Y; V = ¬V; g = ¬Z; Z = ¬Z; Y = ¬Y; e = X ∧ V; Z = Y ∧Z; Z = ¬Z; k = ¬e; Z = Z ∧V; Y = Y ∧ Z; h = f ∧ g; V = X ∧ V; Z = Y ∧ V; i = h ∧ V; V = ¬V; Z = V ∨ Z . Z = h ∨ k. Z = Z ∧ V.
• # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
• # Какой язык L является конкатенацией двух языков: L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?
• # Пусть структурированная программа P: x:= y+1; z := x+1; x := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии σ : σ(x) =3, σ(y) =5, σ(z) =2В каком из следующих состояний σ1 она завершит свою работу?
• # Пусть структурированная программа P: x:= y+1; y := u+1; v := z+1; если x < v то если x = y то z := y+1 иначе z := x конец иначе z :=x +1 конец начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?