Детерминированные и ограниченно-детерминированные функции

1.1. Является ли детерминированной функция φ: {0,1}* → {0,1}*

1) Слово x(1)x(2): отображается в слово 00:0, если существует t, при котором x(t)=0, в противном случае =11:.1

2) s-я буква y(s) в слове φ(x(1)x(2):) равна 0, если при некотором t ≤ s выполняется неравенство x(t)<x(t+1)+x(t+2), в противном случае y(s)=1

1.2. Частичная функция φ: {0,1}* → {0,1}* не определена только на словах вида 00:0. Можно ли доопределить ее до детерминированной?

1) φ (x^ω) = x^ω, если в каждом префиксе слова x^ω число нулей не меньше числа единиц, иначе φ (x^ω) =1^ω

2) φ (x^ω) = y(1)y(2): где y(t)=0, если для некоторого s ≤ t x(s)=1, иначе y(t)=1

1.3. Является ли φ₁ остаточным оператором функции φ?

1) φ: y(1)=0, y(t)=x(t)+y(t-1)+1, φ₁: y(1)=1, y(t)=y(t-1)+1

2) φ: y(1)=1, y(t)=y(t-1)+1, φ₁: y(1)=0, y(t)=y(t-1)+1

1.4. Является ли φ ОД-функцией? Если да, найти ее вес:

1) y(1)=y(2)=1, y(t)=x(t-2) при t ≥ 3

2) y(2t)=x(t+1), y(2t-1)=x(t)+1

3) y(1)=1, y(2t-1)=x(2t-1)+y(2t-3), y(2t)=x(2t-1)

1.5. Частичная функция φ: {0,1}* → {0,1}* определена только на словах вида 0^ω и 1^ω. Доопределить ее до ОД-функции с минимально возможным весом:

1) φ(0^ω) = 0101[100]^ω, φ(1^ω) = 11[10]^ω

2) φ(0^ω) = 01[011]^ω, φ(1^ω) = 1010010001000010:

Список задач по автоматам