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

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

L2 = { b2anb | n > 0 },

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

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

• # Пусть регулярное выражение (ab)*a определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
• # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* →​ {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ε ?
• # Пусть структурированная программа 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 она завершит свою работу?
• # Пусть П+ - это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную z. Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x произведение x · y? [Большая Картинка]
• # Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = 2x2 ?