Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>, где

Какие из следующих трех слов распознаются автоматом A? W= aaabaabab, V= abababaab, U= bbabbbababa

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

• # Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых нет двух подряд идущих 0 ?
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { ww | w = b2anb , n > 0 }, L2 = { b2anb | n > 0 }, L3 = { (ab)nanb | n > 0 }.
• # Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами? P1: x := y+1; z:= x + 1; если x < z то y := z иначе y:=x конецP2: x := y+1; v:= x +1; если x = z то y := v всеP3: x := y+1; u:= z +1; пока u < z +1 делай y := z; u := u+1 все
• # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?
• # Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 ); Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ; Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy; с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?