JFiZO - Zadanie 09.023

• REQUIRE: zadanie 21

Lemat 1: L = L(M) jest pusty, wtw \forall |w| < n: w \notin L, n - ilość stanów automatu M.
Dowód \Rightarrow: trivial
Dowód \Leftarrow: \forall |w| < n: w \notin L. Jeśli w - najkrótsze słowo, |w| >= n, w \in L to z lematu o pompowaniu w = uvy \in L \Rightarrow uy \in L - w nie jest najkrótszym słowem, sprzeczność

• M_1, M_2 - NFA z treści zadania.
• L_1 = L(M_1), L_2 = L(M_2)
• Używając wiedzy z zadania 21 konstruujemy automat rozpoznający (L_1 \cap \overline L_2) \cup (\overline L_1 \cap L_2) - automat ten rozpoznaje słowa które należą do tylko jednego z języków.
• Karmimy ten automat wszystkimi słowami długości < n, n - ilość jego stanów. Jeśli któreś słowo zostanie zaakceptowane to języki nie są równe.

Konstruujemy ten sam automat, rozpoznający (L_1 \cap \overline L_2) \cup (\overline L_1 \cap L_2). Robimy po nim DFS, jeżeli znajdziemy stan akceptujący, to nie są takie same.