IB102 – úkol 6, příklad 2 Odevzdání: 4. 11. 2013
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ = {a, b}. Napište algoritmus, který pro zadanou bezkontextovou
gramatiku G = (N, Σ, P, S) rozhodne, zda jazyk generovaný touto gramatikou obsahuje
alespoň 1 slovo ve tvaru xn
pro nějaké x ∈ Σ a n > 0.
Tedy algoritmus rozhodne, zda gramatika generuje alespoň jedno slovo délky alespoň
1 skládající se pouze z a-ček, nebo pouze z b-ček.
Popište princip fungování vašeho algoritmu a dokažte, že je tento algoritmus konvergentní
(vždy skončí).
Můžete využívat libovolné algoritmy z přednášky, musíte na to však upozornit v textu.
1