IB102 - úkol 8 - řešení
Odevzdání: 15.11. 2010
Vypracoval: James Bond UCO: 007
Skupina: MI6
1. [2 body] Navrhnete algoritmus, který pro zadanou regulární gramatiku rozhodne, zda tato gramatika generuje alespon jedno slovo obsahující symbol a.
Řešeni: PoZadovaný algoritmus muZe vypadat napr. takto: vštup: regularní gramatika G = (N, S, P, S)
1. Nejprve se zbavíme zbyteCnych neterminahí, ze kterých se neda odvodit zadne slovo. To udelame tak, ze si spoďtame mnozinu tech neterminalu, ze kterích se dí odvodit nejake slovo. To se da udelat napr. tak, ze postupne spoďtíme mnoziny Ni, N2, ... neterminalu, ze kterych se da odvodit nejake slovo v 1, 2, ... krocích. Skonďme ve chvíli, kdy N je stejna mnozina jako Ni+1. Víslednou mnozinu nazveme N'.
N1 := {A e N | A — x e P, x e S} i := 0 řepeát i := i + 1
Ni+1 := N u {A e N | A — xB e P, x e S, B e N}
until N = Ni+1 N1 := Ni
2. Nyní míme zaruceno, ze ze vsech neterminílu z N' je mozno odvodit nejake slovo. Dale si tedy spoďtíme mnozinu neterminílu, z nichz je mozno odvodit slovo obsahující a. To jsou vsechny neterminaly s pravidly tvaru A — a, A — aB, kde B e N' (temto neterminalum A ríkejme treba „zíkladní") a vsechny neterminíly, z nichz se dí odvodit vetna forma obsahující zakladní neterminíl. Ty napoďtame obdobním zpusobem jako v predchozím kroku. Víslednou mnozinu nazveme N''.
N := {A e N' | A — a e P} u {A e N' | A — aB e P, B e N'}
i := 0
řepeát
i := i + 1
N+1 := N u {A e N' | A — xB e P, x e S, B e N'}
until N = N+1
N'' := N/
3. Gramatika generuje slovo obsahující a príve tehdy, je-li pocítecní neterminal S v mnozine N''.
vyštup: odpoved' ANO, pokud S e N'', jinak odpoved' NE