Языки, принятые модифицированными версиями конечных автоматов

Детерминированный конечный автомат (DFA) - это модель конечного автомата, способная принимать все и только обычные языки. DFA могут быть (и обычно) определены таким образом, что каждое состояние должно обеспечивать некоторый переход для всех элементов входного алфавита; другими словами, функция перехода $\delta : Q \times \Sigma \rightarrow Q$ должна быть (полной) функцией.

Представьте себе, что мы будем называть дважды детерминированным конечным автоматом (DDFA). Он определяется аналогично DFA, с двумя исключениями: во-первых, вместо перехода, ведущего из одного состояния в другое для каждого возможного входного символа, он должен приводить к двум различным состояниям; во-вторых, чтобы принять строку, все потенциальные пути должны удовлетворять одному или другому из следующих условий:

1. Все потенциальные пути через DDFA приводят к принимающему состоянию (мы будем называть это DDFA типа 1).
2. Все потенциальные пути через DDFA приводят к одному и тому же принимающему состоянию (мы будем называть это DDFA типа 2).

Теперь на мой вопрос:

Какие языки принимают DDFA типа 1 и 2? В частности, это тот случай, когда , л ( Д Д Ж ) = L ( D F ) или L ( Д Д Ж ) ⊊ л ( Д Р ) ? В том случае, если L ( D D F A $L(DFA) \subsetneq L(DDFA)$$L(DDFA) = L(DFA)$$L(DDFA) \subsetneq L(DFA)$ , есть ли простое описание L ( D D F A ) ?$L(DDFA) \neq L(DFA)$$L(DDFA)$

Доказательства (или, по крайней мере, наброски с умеренным содержанием) приветствуются, если они не слишком сложны.

Это в сочетании с ответом Алекса дают полную картину.

можно проверить, адаптировав обычную конструкцию блока питания с измененным условием конечного состояния. В конструкции набора мощностей состояния - это множества состояний исходного автомата. Обычно после выполнения конструкции powerset состояние является конечным, если одно из состояний в наборе является конечным в исходном автомате.$L(DDFA)\subseteq L(DFA)$

• В DDFA типа 1 конечные состояния в построенном автомате - это множества, в которых все элементы являются конечными в исходном автомате.

• В DDFA типа 2 конечные состояния представляют собой одноэлементные множества конечных состояний из исходного автомата.

В обоих случаях полученные автоматы являются DFA.

Теперь type-2DDFA могут выражать только языки и ∅ , в зависимости от того, принимает начальное состояние или нет. Это связано с тем, что оба перехода из одного состояния в другое должны переходить в разные состояния, но принятие возможно только в том случае, если они оказываются в одном и том же состоянии.$\{\epsilon\}$$\emptyset$

Для начала анализа могу сказать, что для типа 1.$L(DFA) \subseteq L(DDFA)$

Вы можете сделать это путем дублирования DFA и добавления ребер в дублированные состояния. Если состояние имеет переход к s 2 на x , вы также делаете переход с s 1 на s ′ 2 на x . Кроме того, s ′ 1 имеет переход к s 2 и s ′ 2 на x . Очевидно, это означает, что мы почти всегда будем в состояниях s i и s ′ $s_1$$s_2$$x$$s_1$$s_2'$$x$$s_1'$$s_2$$s_2'$$x$$s_i$$s_i'$ одновременно (или, возможно, только $s_i$, изначально), и, следовательно, мы узнаем тот же язык.

Обновление: у нас также есть для типа 2, поскольку не существует DDFA типа 2, который распознает язык { a } . Если вы попытаетесь создать такой DDFA, у вас будет начальное состояние s , а затем у вас должно быть два исходящих ребра к состояниям s 1 и s 2 на a , но эти состояния должны быть разными, и, следовательно, два принимающих пути заканчиваются в разных принимающих государствах.$L(DFA) \neq L(DDFA)$$\{ a \}$$s$$s_1$$s_2$$a$

Вместе с ответом Дейва Кларка это дает вам полный анализ.