3. gyakorlat

1. feladat

• \(S\) program és \(F\) feladat \(A\) állapottér felett.
• \(S\) megoldja \(F\)-et

Kérdések:

1. Ha \(F\) nem determinisztikus, akkor \(S\) program sem.

   • Nem, pl
     • \(A = \{1,2\}\)
     • \(F = \{(1,1), (1,2)\}\) - nem determinisztikus
     • \(S = \{1 \to <1>, 2 \to <2>\}\) - determinisztikus

2. Ha az \(F\) determinisztikus, akkor az őt megoldó \(S\) is az.

   • Nem, pl
     • \(A = \{1, 2\}\)
     • \(F = \{1 \to 1\}\) - determinisztikus
     • \(S = \{1 \to <1>, 2 \to <2>, <2,1>\}\) - nem determinisztikus
3. Egy \(S\) nem determinisztikus program, akkor a \(p(S)\) nem determinisztikus.
   • Nem, pl
     • \(S = \{1 \to <1> \; <1, 1, 1>\}\) - nem determinisztikus
     • \(p(S) = \{1 \to 1\}\) - determinisztikus
4. Ha \(p(S)\) nem determinsztikus, akkor \(F\) szintén nem determinisztikus
   • Tipp: igen, mert
     • \(\forall a \in D_F: \; p(S)(a) \subseteq F(a)\)
     • Tehát ha \(p(S)(a)\) nem determinisztikus, akkor \(F(a)\) sem lehet
     • DE! Mi van, ha \(p(S)\) egy olyan \(c\) állapot esetén nem determinisztikus, ami nincs benne a \(D_F\)-ben.
   • másik tipp: nem, mert
     • \(A = \{1,2\}\)
     • \(F = \varnothing\)
     • \(S = \{1 \to <1> \; <1,2>, 2 \to <2>\}\)
     • \(p(S) = \{1 \to 1 \; 2, 2 \to 2\}\)

5. Ha \(F\) determinisztikus, akkor \(p(S)\) is az. (Az előző kérdés fordítva felírva.)

   • nem, mert
     • \(A = \{1,2\}\)
     • \(F = \varnothing\)
     • \(S = \{1 \to <1> \; <1,2>, 2 \to <2>\}\)
     • \(p(S) = \{1 \to 1 \; 2, 2 \to 2\}\)

6. Ha \(F\) nem determinisztikus, akkor \(p(S)\) sem determinisztikus

   • nem
     • \(F=\{1 \to 1 \; 2\}\)
     • \(S = \{1 \to <1>, 2 \to <2>\}\)
     • \(p(S) = \{1 \to 1, 2 \to 2\}\)
7. \(S\) megoldja \(F\)-et. \(\overline{S} \subseteq S\)
   • \(D_{P(\overline{S})} \subseteq D_{P(S)}\)
     • Legyen \(a \in D_{p(\overline{S})}\)
     • Tény: \(\overline{S}(a) \subseteq S(a)\)
     • \(\overline{S}(A) \subseteq \overline{A}^*\)
     • \(S(A) \subseteq \overline{A}^*\)
   • .
     • \(A = \{a\}\)
     • \(S = a \to <a>, <a,a,\dots> \quad \subseteq \quad \overline{S} = \{a \to <a>\}\)
     • \(D_{P(S)} = \varnothing\)
   • \(D_{p(S)} \subseteq S_{p(\overline{S})} \quad \text{ha } \overline{S} \subseteq S\)
     • Legyen \(a \in D_{p(S)}\)
     • \(S(a) \subseteq \overline{A}^*\)
     • \(\overline{S}(a)\subseteq S(a)\)
     • Az előző kettő miatt: \(\overline{S}(a) \subseteq \overline{A}^*\)
   • \(\forall a \in D_{p(s)}: p(\overline{S})(a) \subseteq p(S)(a)\)
     • Legyen \(b \in p(\overline{S})(a)\)
     • \(\exists \alpha \in \overline{S}(a) : \alpha_{|\alpha|}=b\) - van olyan állapot, amelyhez tartozó programsorozattal el tudunk jutni \(b\)-be
     • tény: \(\overline{S} \subseteq S \Rightarrow \overline{S}(a) \subseteq S(a)\)
     • Tehát az is igaz, hogy \(\exists \alpha \in S(a) : \alpha_{|\alpha|}=b\)
     • Ez a programfüggvény definíciója miatt igaz
   • \(D_F \subseteq D_{p(\overline{S})}\)
     • Tény: \(D_F \subseteq D_{p(S)}\), mert \(S\) megoldja az \(F\) feladatot
   • \(\forall a \in D_F: p(\overline{S})(a) \subseteq F(a)\)
     • Tény: \(\forall a \in D_F: p(S)(a) \subseteq F(a)\)
     • \(p(\overline{S})(a) \subseteq p(S)(a)\)
     • Mo. definíciója értelmében az \(\overline{S} \subseteq S\), ezért megoldja a feladatot

3. feladat

• \(S_1\) megoldja \(F\)-et
• \(S_2\) megoldja \(F\)-et

Az \(S_1 \cup S_2\) megoldja-e \(F\)

1. \(S_1 \cup S_2\) program-e?
   • Igen, ha \(S_1\) és az \(S_2\) is program
2. \(D_{p(S_1 \cup S_2)} = D_{p(S_1)} \cap D_{p(S_2)}\)
   • Biz. \(D_{p(S_1 \cup S_2)} = D_{p(S_1)} \cap D_{p(S_2)}\)
     • \(D_{p(S_1 \cup S_2)} \subseteq D_{p(S_1)} \cap D_{p(S_2)}\)
       • Legyen \(a \in D_{p(S_1 \cup S_2)}\)
     • Program függvény definíciója szerint:
       • \((S_1 \cup S_2)(a) \subseteq \overline{A}^*\)
     • Unió definíciója szerint: \((S_1 \cup S_2)(a) = S_1(a) \cup S_2(a)\)
     • Ebből következik, hogy \(S_1(a) \subseteq \overline{A}^*\) és \(S_2(a) \subseteq \overline{A}^*\)
     • Program függvény definíciója miatt:
       • \(a \in D_{p(S_1)}\) és \(a \in D_{p(S_2)}\)
       • \(\Rightarrow a \in D_{p(S_1)} \cap D_{p(S_2)}\)
     • Tehát \(D_{p(S_1 \cup S_2)} \subseteq D_{p(S_1)} \cap D_{p(S_2)}\)
3. \(\forall a \in D_{p(S_1 \cup S_2)}: p(S_1 \cup S_2)(a) = p(S_1)(a) \cup p(S_2)(a)\)
   • Bizonyítás: házi feladat
4. \(D_F \subseteq D_{p(S_1 \cup S_2)}\)
   • Tény:
     • \(D_F \subseteq D_{p(S_1)}\)
     • \(D_F \subseteq D_{p(S_2)}\)
   • Ebből következik, hogy \(D_F \subseteq D_{p(S_1)} \cap D_{p(S_1)}=D_{p(S_1 \cup S_2)}\)
5. \(\forall a \in D_F: p(S_q \cup S_2)(a) \subseteq F(a)\)
   • \(p(S_1)(a) \subseteq F(a)\)
   • \(p(S_2)(a) \subseteq F(a)\)
   • Ebből következik, hogy \(p(S_1)(a) \cup p(S_2)(a) \subseteq F(a)\)
   • Ami \(p(S_1 \cap S_2)(a) \subseteq F(a)\)

+- fogalmak

Változatlan:

• állapot
• állapottér
• program
• program függvény
• megoldás