FORMÁLNÍ JAZYKY A AUTOMATY I
ŘEŠENÍ cvičení 1.
1. Všechny jazyky jsou podmnožinou jazyka L\. Dále platí:
Li = 1/6: inkluze Lq C Li je zřejmá. Ukážeme opačnou inkluzi, t.j. L\ C Lq.
Zřejmě prázdné slovo je prvkem obou jazyků. Každé neprázdné slovo tu G L\ může být nazíráno jako posloupnost, ve které se střídají skupiny symbolů a se skupinami symbolů 6. Přesněji, slovo tu můžeme zapsat jako tu = a11 V1 ... aln Wn, kde i\ > 0; ji,Í2,... ,in>0; in > 0; n > 1 a ň + jn > 0.
Předpokládejme, že jn > 0, tzn. slovo tu končí skupinou symbolů 6 (případ jn = 0 se řeší analogicky). Indukcí vzhledem k n prokážeme, že tu G {a*b}*. 1°. tu = ahV^ = ailba0ba°b    a°b. Proto tu G {a*b}j».
2°. Podle indukčního předpokladu tvrzení platí pro n. Dokážeme jej pro n + 1. Slovo tu obsahující n + 1 skupin symbolů b můžeme napsat jako zřetězení slov v\ ai)2, kde v\ = a^V1 ... a%nVn a»2 = al"+16J'"+1. Podle IP obě slova patří do {a*b}*, a proto slovo tu patří do {a*b}*.
L2 C Li: slovo aa £ L2 ale aa G L\.
L3 c Li: slovo baab £ L3 ale baab G L\.
L4 c L3: Jestli w G L4, pak z definice operace zřetězení jazyků plyne existence slov v\,v2,v3 takových, že v\ = a, v2 = a1 a v3 = V {i, j > 0). Slova V1V2 a v3 dokazují příslušnost slova w do I3. Inkluze je ostrá, protože e £ L4.
L4 c L5: Podobně jako v předcházejícím případě.; v\ G {a} a v2v3 G {a, b}*. Inkluze je ostrá, protože slovo ba £ L 4 ale ba G L5.
L5 c Li: slovo bb £ L5 ale bb G L\. Všechny zbývající dvojice jsou nesrovnatelné.
2. a) X = {00}* • {1000,0100,0010,0001,00}- {00}*.
b) Označme L = {0,1}*. Pak
Y = (£{000}!: U L{111}L)C n [{1}L{1} U {0}L{0} U {0} U {1}].
3. Buď tu G (Li U L2) ■ L3.
w = u - v, kde v G L3 a u G L\ anebo u G L2. -<=>■ u ■ v G Li ■ L3 anebo u ■ v G L2 ■ L3 <í=^ tu G (L1-L3)U(L2-L3).
Pro Li = {a}, L2 = {aa} a L3 = {a,aa} rovnost b) neplatí.
4. Buď tu e (£1 • L2)+ ■ L1 <^
tu = uv, kde v G L\ a u G (Li ■ L2)+ <í=^
tu = uv, kde v G L\ a u = x\y\... xnyn, kde Xi G L\ a t/j G L2 pro i = 1,... , n. -<=>■ tu = UV, kde U = x\ G L\ a V = y\x2 ■ ■ ■ ynv G (L2 • L{)+ -í=^> tu G Lx ■ (L2 ■ Ia)+.
Rovnost (Li ■ L2)° ■ Li = Li = Li ■ (L2 ■ Li)0 je zřejmá. Pro Lx = {a}, L2 = {b} rovnost b) neplatí; slovo ba G (la U L2)* ale ba ^ L\{L\ ■ L2)*
5. a) /z-1 (aabaaabaa) = {ababc, abccbc, ccbabc, ccbccbc}.
b) h(L) = {tu G {a, 6}* | jta(w) = 3jti,(tu); tu neobsahuje podřetězec 66}.
c) /i_1(i) = {w G {a, c}* I )te(tu) je sudý}.