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

16

Детерминированный конечный автомат (DFA) - это модель конечного автомата, способная принимать все и только обычные языки. DFA могут быть (и обычно) определены таким образом, что каждое состояние должно обеспечивать некоторый переход для всех элементов входного алфавита; другими словами, функция перехода δ:Q×Σ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)L(DDFA)L(DDFA)=L(DFA)L(DDFA)L(DFA) , есть ли простое описание L ( D D F A ) ?L(DDFA)L(DFA)L(DDFA)

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

Patrick87
источник

Ответы:

9

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

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

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

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

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

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

Дэйв Кларк
источник
7

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

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

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

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

Алекс тен Бринк
источник
Очень приятно разглядеть этот встречный пример для типа 2!
Дэйв Кларк,
@ Дэйв Кларк: спасибо. Это немного глупый пример, но он работает :)
Алекс тен Бринк
«Патологический» вместо «глупый».
Дейв Кларк,
Очень хорошая работа, ребята. Было четыре вещи, которые нужно проверить, и у каждого из вас есть две. Если вы не возражаете, я выберу @DaveClarke в качестве ответа, только потому, что у него меньше представителей, чем у Алекса.
Patrick87
1
В связи с этим вы хотели бы подробнее рассказать о языках, принятых в DDFA типа 2, или мне следует задать отдельный вопрос и дать ссылку на него?
Patrick87