IB102 ­ úkol 4 ­ řešení Odevzdání: 13. 10. 2008 Vypracoval: James Bond UČO: 007 Skupina: MI6 1. [2 body] Určete počet jazykově různých (akceptujících různý jazyk) minimálních deterministických automatů s totální přechodovou funkcí nad abecedou = {a}, které mají právě n stavů a právě jeden akceptující stav. Odpověď zdůvodněte. Řešení: Pro případ n = 1 existuje zřejmě pouze jeden automat vyhovující podmínce - akceptuje jazyk . Mějme nyní automat, který ma více stavů než 1 (n > 1). Aby byl automat minimální, nesmí v něm být nedosažitelné stavy. A protože je deterministický a totální, z každého stavu existuje právě jeden přechod pod a. Automat tedy musí vypadat jedním z těchto dvou způsobů: 1. //GFED@ABCa1 a //GFED@ABCa2 a // . . . a // GFED@ABCan a 2. //GFED@ABCa1 a // . . . a //GFED@ABCai a // . . . a // GFED@ABCan a gg , i = n Diskutujme nyní umístění akceptujícího stavu: * Je-li v části před cyklem, musí to být pouze v případě automatu typu 1. Jinak by automat nebyl minimální ­ mohli bychom stavy z cyklu sloučit do jednoho a automat by přijímal stále stejný jazyk. Musí to být také stav těsně předchazející smyčce, jinak bychom mohli následujicí stavy až ke smyčce odstranit. Máme tedy pouze jednu možnost, kde může být akceptující stav, pokud není v cyklu. Ještě je třeba zdůvodnit, proč je tento automat minimální - přijímá jednoslovný jazyk {an-2 }, který totálním automatem s méně než n stavy nejsme schopni rozpoznat (zřejmé). * Je-li jedním ze stavů v cyklu, můžeme akceptující stav umístit do stavu an a přechod z tohoto stavu může vést do libovolného stavu ai. Tímto vytvoříme automat, který přijímá jazyk {ai-1 ax | x mod (n - i + 1) = n - i} (pokud cyklus obsahuje stavy ai až an ­ viz druhý obrázek ­ a akceptující je stav an, i n). Těchto automatů je n. Další možností je, že ze stavu an vede přechod do stavu a1, tedy všechny stavy automatu jsou v jednom velkém cyklu. Potom můžeme umístit akceptující stav do libovolného stavu a automat bude přijímat jiný jazyk (pokud je ak akceptující stav, tak {ax | x mod n = k-1}. Těchto automatů je také n, ale jeden jsme již započítali v předchozím případě (případ, že akceptuje stav an). Tedy máme dalších n - 1 automatů. Oba dva tyto typy automatů je také zřejmě minimální. Kdyby automat vypadal nějak jinak ­ měl by cyklus, kterém by nebyly všechny vrcholy a akceptující stav by byl jiný než an, potom by automat nebyl minimální; intuitivně část větve před cyklem bychom mohli "zasunout" do cyklu, viz příklad na obrázku: //GFED@ABCa1 a //GFED@ABCa2 a //GFED@ABCa3 a //GFED@ABC?>=<89:;a4 a //GFED@ABCa5 a gg //GFED@ABCa1 a //GFED@ABCa5 a //GFED@ABCa3 a //GFED@ABC?>=<89:;a4 a gg Pro n = 1 existuje tedy pouze jeden automat vyhovující zadání, pro n > 1 jich existuje 1 + n + n - 1 = 2n. IB102 ­ úkol 4 ­ řešení Odevzdání: 13. 10. 2008 Vypracoval: James Bond UČO: 007 Skupina: MI6 2. [2 body] Nechť = {a, b} je abeceda a X a Y jsou relace na . Pro každou z nich rozhodněte, zda je pravou kongruencí (rozhodnutí zdůvodněte). Pokud ano, udejte počet tříd rozkladu /X resp. /Y a uvedťe alespoň jednoho reprezentanta každé třídy. a) [1 bod] X : u X v |u| = k |v| pro alespoň jedno k {1 2 , 1, 2} b) [1 bod] Y : u Y v (|u| + |v|) mod 2 = 0 Řešení: a) Relace X není tranzitivní: kupříkladu b X bb a bb X bbbb, ale b X bbbb. Tedy X není ekvivalencí a proto nemůže být ani pravou kongruencí. b) Definice u Y v se dá přepsat slovně jako "délka součtu slov u a v je sudá". Relace Y je ekvivalencí, jelikož je ­ reflexivní: Dvojnásobek délky libovolného slova je sudé číslo. ­ symetrická: Pokud |u| + |v| je sudé, pak je i |v| + |u| sudé. ­ tranzitivní: |u|+|v| je sudé právě když |u| i |v| jsou obě sudé nebo obě liché. Proto z u Y v a v Y w plyne, že |u|, |v|, |w| jsou buď všechny sudé nebo všechny liché a tudíž u Y w. Nyní dokážeme, že Y je i pravou kongruencí. Nechť u Y v, tedy |u| + |v| je sudé. Pak pro libovolné slovo w platí, že součet |uw| + |vw| = |u| + |v| + 2|w| je také sudý a proto uw Y vw. Existují dvě třídy rozkladu. Jedna obsahuje všechna slova ze liché délky, druhá všechna slova ze sudé délky: /Y = {[a], [ab]}.