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.

Alt

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.

 
jfizo/zadanie09.023.txt · ostatnio zmienione: 2010/03/14 19:25 przez alistra
 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Recent changes RSS feed