FORMÁLNÍ JAZYKY A AUTOMATY I
Řešení sady problémů 3.
1. Automat A\ obsahuje nedosažitelný stav qg. Při aplikaci algoritmu pro minimalizaci konečného automatu obdržíme postupně následující třídy ekvivalentních stavů:
• I = {qo, 92, 93, 94, 95, 96, 97,9lo}
II = {Qi,Qs}
• h = {9o,92>
h = {93,94,96,9io} h = {95,97} II = {9i, 98 }
• /1 = {90,92} 4 = {93}
4' = Í94,9e} IT = {9io}
-Í3 = {95,97} II = {91, 98 }
Automat A2 neobsahuje nedosažitelné stavy a je minimální. Po převedení obou automatů do kanonického tvaru obdržíme v obou případech následující automat:
=[{1,2,3,4,5,6}, {a, 6}, 5,1, {1}]
6(1, a) = 2
5(1,6) = 3
0(2, a) = 4
5(2,6) = 1
5(3, a) = 1
5(3,6) = 5
5(4, a) = 6
5(4,6) = 2
5(5, a) = 3
5(5,6) = 6
5(6, a) = 6
5(6,6) = 6
Tedy automaty A\ a A2 jsou ekvivalentní.
2. Deterministický konečný automat je určen následující tabulkou:
		a	b
—►	0	0	01
	01	02	012
	02	03	013
	03	04	014
i—	04	0	01
	012	023	0123
	013	024	0124
i—	014	02	012
	023	034	0134
i—	024	03	013
i—	034	04	014
	0123	0234	01234
i—	0124	023	0123
i—	0134	024	0124
i—	0234	034	0134
i—	01234	0234	01234
3. Je třeba dokázat dvě inkluze:
L(G) C L :
Dokážeme, že pro libovolnou větnou formu w, kde S =>■* w, platí: 2(#a(w) + #a(w)) = + Důkaz provedeme indukcí vzhledem k délce odvození větné formy w.
. n=0: - pak w = S a 2(#jl(S) + #a(5)) = 0 = +
• indukční krok: Předpokládejme, že tvrzení platí pro každou větnou formu, jejíž délka odvození je n. Ukážeme, že pak toto tvrzení platí též pro každou větnou formu, která má délku odvození n + 1. Nechť w je větná forma o délce odvození n + 1 a nechť S =>■ v\ =>■ • • • =>■ vn =>■ w je její odvození v gramatice G. Větná forma vn má délku odvození n, proto dle indukčního předpokladu platí:
2(#^K) + #aW) = #*(«„) + #b(yn)
Derivace vn =>■ w vznikla aplikací jednoho z následujících pravidel:
- S ->• ABBS nebo 5 ->• ABB. Pak:
^(w) + #„(«;) = #,4(i;n) + #„(«„) + 1 a #b{w) + #b(w) = #B{vn) + #b{vn) + 2 a tedy
- AB ->• BA, BA ->• AS, A ->• a nebo B -t b. Pak:
#.4(w) + #a(w) = #A{vn) + #a{vn) a
+ = #B{vn) + #b{vn), tedy
Každé slovo u jazyka L(G) je větná forma, která neobsahuje neterminály. Proto 2.#a(u) = #*(u).
L C L(G) :
Nechť u G L. Ukážeme, že slovo u lze odvodit v gramatice G. Nechť n = #a(u)- Pro odvození slova u v gramatice G nejprve aplikujeme (n — 1) krát pravidlo S —> ABBS a pak jedenkrát pravidlo S —> ABB. Obdržíme větnou formu w = (ABB)n, pro niž platí #a(w) = #a(w) A = #íj(m). Nyní pomocí opakované aplikace pravidel AB —> BA
a BA —> AB přepíšeme větnou formu w na větnou formu w' tak, aby platilo:
Mi € N, 1 < i < 3n : na i-tém místě ve slově u je a -<=>■
na i-tém místě ve větné formě w' je A
4. a) Nechť A je konečný automat s k stavy akceptující jazyk L.
' =>■' Z nekonečnosti jazyka L plyne existence slova w G L délky |w\ >k. Když | w| < 2fc, tvrzení je dokázáno. Předpokládejme \w\ > 2k. Na slovo w můžeme aplikovat pumping lemu. Ta zaručuje existenci slov v,x,y takových, že x ^ e, \x\ < k, w = vxy a vy € L. Délku slova vy můžeme ohraničit takto: \w \ — k < \vy\ < \w\. Nyní buď \vy\ < 2k, anebo pro něj můžeme uvedenou úvahu zopakovat. Protože se vždy slovo zkrátí minimálně o jeden a maximálně o k symbolů, jeho délka po konečném poctě zkracování bude náležet do intervalu < k, 2k) délky k.
' -4=' Opačná inkluze plyne přímo z pumping lemy: současně se slovem w délky alespoň k musí L obsahovat slova vxly pro všechna i > 0, přičemž w = vxy a x ^ e.
b) Tvrzení obecně neplatí. Jako protipříklad stačí vzít např. automat A akceptující jazyk {abc}*; A = ({q0,qi,q2},{a,b,c},ô,q0,{q0}), kde S(q0,a) = qi, 5{q1,b) = q2 a <%2,c) = q0.