Różnica między językami akceptowanymi przez dwa DFA o różnych stanach początkowych / stanach akceptacji?

Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki.

Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany końcowe (akceptujące) mogą być różne. Niech i być języki akceptowane przez i , odpowiednio. $A = (Q, \Sigma, \delta, q_1, F_1)$ $B = (Q, \Sigma, \delta, q_2, F_2)$ $A$ $B$ $L_1$ $L_2$ $A$ $B$

Istnieją cztery przypadki:

$q_1 = q_2$ i . $F_1 = F_2$
$q_1 \neq q_2$ i . $F_1 = F_2$
$q_1 = q_2$ i . $F_1 \neq F_2$
$q_1 \neq q_2$ i . $F_1 \neq F_2$

Moje pytanie brzmi

Jakie są różnice między i w przypadkach 2, 3 i 4? $L_1$ $L_2$

W związku z tym mam bardziej szczegółowe pytanie,

Przejściowa monoida automatu jest zbiorem wszystkich funkcji w zestawie stanów indukowanych przez łańcuchy wejściowe. Zobacz stronę po więcej szczegółów. Przejściowy monoid można uznać za monoid działający na zbiór stanów. Zobacz tę stronę Wiki, aby uzyskać więcej informacji.

W wielu literaturach automat jest nazywany silnie połączonym, gdy działanie monoidu jest przechodnie, tzn. Zawsze istnieje co najmniej jedno przejście (ciąg wejściowy) z jednego stanu do drugiego.

Jeśli i są silnie połączonymi automatami, jakie są różnice między i w przypadkach 2, 3 i 4 powyżej? $A$ $B$ $L_1$ $L_2$

Jakaś literatura szczegółowo omawia te kwestie?

Przeszukałem wiele książek i artykułów i jak dotąd nie znalazłem nic pomocnego. Uważam, że nie mam jeszcze odpowiednich słów kluczowych. Dlatego szukam pomocy. Wszelkie wskazówki / referencje będą bardzo mile widziane.

formal-languages reference-request finite-automata scaaahu
źródło

Co rozumiesz przez „jakie są różnice”? Chcesz wiedzieć, czy i mogą / muszą różnić się w przypadkach 2,3,4?

L_{1}

$L_1$

L_{2}

$L_2$

Hendrik Jan

@HendrikJan Jeśli przeczytasz odpowiedź Shaull podaną poniżej, zrozumiesz i mogą się różnić. (Użył i ). Nie wiem, czy muszą się różnić. To część mojego pytania. Zapytałem „jakie są różnice?”. Nie sugerowałem, że muszą się różnić.

L_{1}

$L_1$

L_{2}

$L_2$

L (A)

$L(A)$

L (B)

$L(B)$

scaaahu

Odpowiedzi:

Ponieważ są silnie połączone, to jeśli , istnieją słowa takie, że i . $A,B$ $q_1\neq q_2$ $p_1,p_2$ $\delta(q_1,p_1)=q_2$ $\delta(q_2,p_2)=q_1$

Rozważ przypadek 2, a następnie iff i iff . Możesz więc dodać prefiks, aby przełączać języki. $w\in L(A)$ $p_2w\in L(B)$ $x\in L(B)$ $p_1 x\in L(A)$

Rozważmy przypadek 3, a następnie - silną łączność najwyżejsłowa takie, że dla każdego masz i podobnie w innym kierunku (od do ). $|F_1|$ $s_1,...,s_k$ $q_i\in F_1$ $\delta(q_i,s_i)\in F_2$ $B$ $A$

W ten sposób możesz tworzyć sufiksy, aby przełączać się między językami.

Łącząc je, można scharakteryzować różnice za pomocą przedrostków i przyrostków. Na przykład, w przypadku 4, iff w dla niektórych w z góry określonym zestawie skończonym. $w\in L(B)$ $p_1 w s_i$ $L(A)$ $s_i$

W rzeczywistości możesz nawet powiedzieć coś interesującego o tych słowach: zdefiniuj jako DFA, gdzie jest stanem początkowym, a jest stanem końcowym, a w przypadku 2 masz (i podobnie w innym kierunku). $C$ $q_1$ $q_2$ $L(B)=L(C)\cdot L(A)$

Jeśli chodzi o przyrostki, rzeczy są bardziej zaangażowane, ponieważ nie można z góry określić, w jakim stanie końcowym skończysz. Nie jestem pewien, czy możesz napisać to jako konkatenację, ale możesz napisać gdzie jest DFA uzyskanym z ustawienia be , a to DFA, który rozpoczyna się w ze stanami końcowymi . $L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$ $A_q$ $A$ $F=\{q\}$ $E_q$ $q$ $F_2$

W przypadku 4 możesz połączyć oba.

Być może martwisz się, że nie jest to prawdziwa odpowiedź, ale raczej charakterystyka właściwości za pomocą słów zamiast stanów, ale jest to typowa odpowiedź w tej dziedzinie (podobnie jak twierdzenie Myhill-Nerode).

Shaull
źródło

Rozumiem twoją odpowiedź. Mój problem polega na tym, że np. Takie nie jest unikalne, tzn. Istnieje wiele takich, że . Tak więc istnieje wiele prefiksów w różnicy między i . Czy mamy bardziej precyzyjne odpowiedzi?

p_{1}

$p_1$

p_{1}

$p_1$

δ (q_{1}, p_{1}) = q_{2}

$\delta(q_1,p_1) = q_2$

L (A)

$L(A)$

L (B)

$L(B)$

scaaahu

Zredagowałem odpowiedź, podając bardziej precyzyjne informacje.

Shaull

Naprawdę podoba mi się pomysł, że DFA . Wydaje mi się, że mam ogólny pomysł na rozwiązanie przypadku 3 i 4. Bardzo dziękuję. Zaczekam chwilę, zanim zaakceptuję tę odpowiedź.

C

$C$

scaaahu

Pamiętaj o dodatkowych zmianach w poście.

Shaull

Dobry pomysł. Przyjmujesz jeden stan naraz, a potem bierzesz związek. Mam nadzieję, że moja interpretacja jest poprawna.

scaaahu