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:

Wszystkie potencjalne ścieżki przez DDFA prowadzą do stanu akceptacji (nazwiemy to DDFA typu 1).
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 , , czy ? W przypadku, gdy , czy istnieje łatwy opis ? $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.

formal-languages automata finite-automata

— Patrick87
źródło

Odpowiedzi:

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$

— Dave Clarke
źródło

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. $L(DFA) \neq L(DDFA)$ $\{ a \}$ $s$ $s_1$ $s_2$ $a$

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

— Alex ten Brink
źródło

Bardzo miło jest dostrzec ten licznik dla typu 2!

— Dave Clarke

@Dave Clarke: dzięki. To trochę głupi przykład, ale działa :)

— Alex ten Brink

„Patologiczny” zamiast „głupiego”.

— Dave Clarke

Bardzo fajna robota chłopaki. Były cztery rzeczy do sprawdzenia i każdy z was ma dwie. O ile żaden z was nie sprzeciwia się, wybiorę @DaveClarke jako odpowiedź, tylko dlatego, że ma mniej przedstawicieli niż Alex.

— Patrick87

Czy w powiązanej notatce chciałbyś omówić języki akceptowane przez DDFA typu 2, czy powinienem zadać osobne pytanie i link do tego?

— Patrick87