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

 

 

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 остаточным оператором функции φ?

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

2) φ: y(1)=1, y(t)=y(t-1)+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…

 

 

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