IB102 – úkol 12, příklad 3 – bonus Odevzdání: 17. 12. 2012
Vypracoval(a): UČO:
Skupina:
3. [3 body] Sestrojte gramatiku typu 0, která generuje jazyk
L = {a1
ba2
b . . . an
b | n ≥ 1}.
Řešení: Gramatika G = ({S, A, K, Q, Z1, Z2, Z3}, {a, b}, P, S), kde
P = {S → Z1AZ2K,
AZ2 → Z2aA,
Aa → aA,
Z1Z2a → aZ1Z2,
Z1Z2A → bZ1Z3A | bQ,
Z3A → AZ3,
Z3K → AZ2K,
QA → Q,
QK → }.
Intuitivně, Z1, Z2, Z3 fungují jako zarážky, neterminál K znáčí konec větné formy. Cokoliv
je před zarážkou Z1 už zůstává tak, jak je, mezi zarážkou Z1 a neterminálem K probíhá
generování áček, která se pak přesunou před zarážku Z1. Například slovo ab odvodíme v
gramatice G takto:
S ⇒ Z1AZ2K ⇒ Z1Z2aAK ⇒ aZ1Z2AK ⇒ abQK ⇒ ab
Slovo abaab odvodíme takto:
S ⇒ Z1AZ2K ⇒ Z1Z2aAK ⇒ aZ1Z2AK ⇒ abZ1Z3AK ⇒ abZ1AAZ2K ⇒ abZ1AZ2aAK ⇒
abZ1Z2aAaAK ⇒ abZ1Z2aaAAK ⇒ abaZ1Z2aAAK ⇒ abaaZ1Z2AAK ⇒ abaabQAK ⇒
abaabQK ⇒ abaab