Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?

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

• # [Большая Картинка] Какую булеву функцию реализует эта логическая схема в вершине a ?
• # Какие из следующих трех конечных автоматов Ai = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φi> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ? [Большая Картинка]
• # Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
• # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
• # Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0] задает функцию F(x) = [ log2 (x+1) ] (целая часть двоичного логарифма x+1) ?