Języki akceptowane przez zmodyfikowane wersje automatów skończonych

Deterministyczny automat skończony (DFA) to model maszyny stanów zdolny do przyjmowania wszystkich i tylko zwykłych języków. DFA można (i zwykle są) definiować w taki sposób, że każdy stan musi zapewnić pewne przejście dla wszystkich elementów alfabetu wejściowego; innymi słowy, funkcja przejścia $\delta : Q \times \Sigma \rightarrow Q$ powinna być funkcją (całkowitą).

Wyobraź sobie, co nazwiemy podwójnie deterministycznym automatem skończonym (DDFA). Jest on zdefiniowany podobnie do DFA, z dwoma wyjątkami: po pierwsze, zamiast przejścia prowadzącego z jednego stanu do drugiego dla każdego możliwego symbolu wejściowego, musi on prowadzić do dwóch różnych stanów; po drugie, aby zaakceptować ciąg, wszystkie potencjalne ścieżki muszą spełniać jeden lub drugi z następujących warunków:

1. Wszystkie potencjalne ścieżki przez DDFA prowadzą do stanu akceptacji (nazwiemy to DDFA typu 1).
2. Wszystkie potencjalne ścieżki przez DDFA prowadzą do tego samego stanu akceptacji (nazwiemy to DDFA typu 2).

Teraz moje pytanie:

Jakie języki są akceptowane przez DDFA typu 1 i typu 2? W szczególności, czy jest tak, że , L (DDFA) = L (DFA) , czy L (DDFA) \ subsetneq L (DFA) ? W przypadku, gdy L (DDFA) \ neq L (DFA) , czy istnieje łatwy opis L (DDFA) ?L ( D D F A ) = L ( D F A ) L ( D D F A ) ⊊ L ( D F A ) L ( D D F A ) ≠ L ( D F A ) L ( D D $L(DFA) \subsetneq L(DDFA)$$L(DDFA) = L(DFA)$$L(DDFA) \subsetneq L(DFA)$$L(DDFA) \neq L(DFA)$$L(DDFA)$

Doceniane są dowody (lub przynajmniej średnio rozwinięte szkice), jeśli nie są zbyt skomplikowane.

To w połączeniu z odpowiedzią Alexa daje pełny obraz.

$L(DDFA)\subseteq L(DFA)$ można udowodnić, dostosowując zwykłą konstrukcję zestawu zasilającego do zmodyfikowanego stanu końcowego. W konstrukcji zestawu mocy stany są zestawami stanów z oryginalnego automatu. Zwykle po wykonaniu konstrukcji zestawu zasilającego stan jest ostateczny, jeśli jeden ze stanów w zestawie jest końcowy w oryginalnym automacie.

• W DDFA typu 1, stanami końcowymi w zbudowanym automacie są zbiory, w których wszystkie elementy są ostateczne w automacie oryginalnym.

• W DDFA typu 2 stany końcowe są zestawami singletonów stanów końcowych z oryginalnego automatu.

W obu przypadkach wynikowymi automatami są DFA.

Teraz typ 2DDFA może wyrażać tylko języki i , w zależności od tego, czy stan początkowy akceptuje, czy nie. Wynika to z faktu, że dwa przejścia ze stanu muszą przejść do różnych stanów, ale akceptacja jest możliwa tylko wtedy, gdy staną się w tym samym stanie.$\{\epsilon\}$$\emptyset$

Aby rozpocząć analizę, mogę powiedzieć, że dla typu 1.$L(DFA) \subseteq L(DDFA)$

Możesz to zrobić, kopiując DFA i dodając krawędzie do zduplikowanych stanów. Jeśli stan ma przejście do na , również przejdziesz z do na . Ponadto ma przejście do i na . Oczywiście oznacza to, że prawie zawsze będziemy w stanach i w tym samym czasie (lub ewentualnie tylko , początkowo), a zatem rozpoznamy ten sam język.$s_1$$s_2$$x$$s_1$$s_2'$$x$$s_1'$$s_2$$s_2'$$x$$s_i$$s_i'$$s_i$

Aktualizacja: mamy również dla typu 2, ponieważ nie istnieje DDFA typu 2, który rozpoznaje język . Jeśli spróbujesz utworzyć taki DDFA, masz stan początkowy , a następnie musisz mieć dwie krawędzie wychodzące do stanów i na , ale te stany muszą być różne, a zatem dwie ścieżki akceptacji kończą się inaczej przyjmowanie stanów.{ a } s s 1 s 2$L(DFA) \neq L(DDFA)$$\{ a \}$$s$$s_1$$s_2$$a$

Wraz z odpowiedzią Dave'a Clarke'a daje to pełną analizę.