5.4. Конечные преобразователи Уотсона–Крика 213
Отметим, что в предыдущих результатах заключительные
состояния роли не играли, так как они нисколько не увеличи-
вают порождающую силу конечных автоматов Уотсона–Крика
по модулю детерминированной ОПМ или в некоторых случаях
по модулю слабого кодирования. Кроме того, отметим, что про-
стых конечных автоматов Уотсона–Крика (всего лишь с тремя
состояниями) достаточно для характеризации RE по модулю
слабого кодирования. Автоматы без состояний, использующие
переходные пары
u
v
без дополнительных ограничений, нало-
женных на строки u, v, также оч ень сильны. Эти наблюдения
вновь и ллюстри руют мощь комплементарности Уотсона–Кри-
ка и они еще подтвердятся ниже пр и рассмотрении других уст-
ройств.
Стоит также упомянуть, что в большинстве приведен-
ных выше конструкций (имеются в виду доказательства
теоремы 5.5 и лемм 5.14 и 5.16) в качестве отношения ком-
плементарности бралось отношение равенства, т. е. (a, b) ∈ ρ
означало a = b. Это не относится к доказательству теоре-
мы 4.12, а значит, и к теореме 5.2. Как уже неоднократно
отмечалось, в молекуле ДНК отношение комплементарности
взаимно однозначно. Поэтому если мы пытаемся следовать
«реалиям ДНК», то мы долж ны считать основное отноше-
ние комплементарности для наших моделей симметричным и
взаимно однозначным. Из-за этого могут возникнуть некото-
рые проблемы, поскольку в доказательстве теоремы 4.12 уже
было использовано отношение, не являющееся даже инъектив-
ным: (s, s) ∈ ρ и в то же время
s, [s, k]
∈ ρ.
5.4 Конечные преобразователи Уотсона–Крика
Выходную последовательность можно связать с конечным
автоматом Уотсона–Крика тем же способом, каким такая
последовательность связывается с конечным автоматом в
виде ОПМ. Выходная посл едова тельн ость записывается на
обычной ленте, в отличие от вход ной, записанной на двойной
ленте Уотсона–Крика (иная возможность будет рассмотрена в
разделе 5.6). Рис. 5.4 иллюстрирует эту идею.