IB102 – úkol 8, příklad 1 – řešení Odevzdání: 12. 11. 2012
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Navrhněte algoritmus, který pro zadanou regulární gramatiku G rozhodne, zda
tato gramatika generuje alespoň jedno slovo sudé délky (0 je sudé číslo).
Řešení může vypadat například takto:
Na vstupu máme regulární gramatiku G = (N, Σ, P, S), na výstupu odpověď na zadanou
otázku ve formě True nebo False.
Algorithm 1 Test na přítomnost slova sudé délky v regulární gramatice
1: if existuje pravidlo S → ε then
2: return True 0 je sudé číslo
3: end if
4: i ← 1 inicializace 1. počítadla
5: ii ← 1 inicializace 2. počítadla
6: neterminály, které se dají přepsat na slovo sudé délky rovné nejvýše i
7: Ri
s ← {X ∈ N | X → ∈ P}
8: neterminály, které se dají přepsat na slovo liché délky rovné nejvýše i
9: Ri
l ← {X ∈ N | X → a ∈ P pro nějaké a ∈ Σ}
10: repeat
11: i ← ii
12: ii ← i + 2
13: neterminály, které se dají přepsat na slovo délky nejvýše i se jistě dají přepsat na
slovo délky nejvýše i + 2
14: Rii
s = Ri
s
15: Rii
l = Ri
l
16: for all X ∈ Ri
l do pokud lze X přepsat na slovo liché délky rovné nejvýše i
17: for all Z → aX ∈ P, kde a ∈ Σ a Z ∈ N do pak neterminál Z
18: Rii
s ← Rii
s ∪ {Z} lze přepsat na slovo sudé délky rovné nejvýše i
19: end for
20: end for
21: for all X ∈ Ri
0 do pokud lze X přepsat na slovo sudé délky rovné nejvýše i
22: for all Z → aX ∈ P, kde a ∈ Σ a Z ∈ N do pak neterminál Z
23: Rii
l ← Rii
l ∪ {Z} lze přepsat na slovo liché délky rovné nejvýše i
24: end for
25: end for
26: if S ∈ Rii
s then
27: return True
28: end if
29: until Rii
s = Ri
s ∧ Rii
l = Ri
l opakujeme, dokud nám přibývají neterminály v počítaných
množinách oproti minulé iteraci cyklu
30: return False