Детерминированные и ограниченно-детерминированные функции
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…
Список задач по автоматам
| 
