IB102 – úkol 2, příklad 2 Odevzdání: 29. 9. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body]
a) [1 bod] Uvažte abecedu Σ = {a, b} a gramatiku G generující jazyk nad touto abecedou
definovanou následovně:
G = ({S, A, B}, Σ, P, S)
P = {S → ε | a | aA | b | bB,
A → a | aA | b | bB,
B → b | bB}
Jazyk L = L(G) generovaný touto gramatikou popište pomocí libovolných konečných
jazyků a operací sjednocení, průnik, zřetězení, iterace, pozitivní iterace a doplněk.
Rada: čím jednodušeji si jazyk L zapíšete, tím snáze se vám bude řešit část (b).
b) [1 bod] Vytvořte regulární gramatiku G generující doplněk jazyka L, tedy L(G) =
co−L. Zapište ji včetně všech formálních náležitostí.