Příklad 1.
Navrhněte regulární gramatiku pro jazyk
L = {w | w ∈ {a, b}∗
, |w| = 3k, k ∈ N0}.
Příklad 2.
Navrhněte bezkontextovou gramatiku pro jazyk
L = {w ∈ {a, b, c}∗
, a(w) + b(w) = c(w)}.
Příklad 3.
Mějme gramatiku G = ({S, A, B, C}, {a, b, c}, P, S), kde P = {
S → aA | bS | cS
A → aA | bB | cS
B → aA | bC | cS | b
C → a | b | c | aC | bC | cC }
Jakého typu je gramatika G podle Chomského hierarchie. Určete jazyk L =
L(G), který generuje gramatika G.
Příklad 4.
Navrhněte regulární gramatiku pro jazyk
L = {w ∈ {a, b, c}∗
| w neobsahuje podslovo cac}.
Příklad 5.
Mějme gramatiku G = ({S00, S01, S02, S10, S11, S12}, {a, b, c}, P, S00), kde P = {
S00 → aS10 | bS01 | cS00
S01 → aS11 | bS02 | cS01 | ε
S02 → aS12 | bS00 | cS02
S10 → aS00 | bS11 | cS10
S11 → aS01 | bS12 | cS11
S12 → aS02 | bS10 | cS12 }
Úkoly:
• Jakého typu je gramatika G podle Chomského hierarchie?
• Určete jazyk L = L(G), který generuje gramatika G.
• Není-li gramatika G regulární, proveďte změny v pravidlech tak, aby G
byla regulární.
1
Příklad 6.
Navrhněte regulární gramatiku pro jazyk
L = {w ∈ {a, b}∗
, a(w) = 2k, b(w) = 2l + 1, k, l ≥ 0}.
Příklad 7.
Navrhněte regulární gramatiku pro jazyk
L = {w ∈ {0, . . . , 9}∗
, w je zápis přirozených čísel dělitelných 5}.
Příklad 8.
Navrhněte regulární gramatiku pro jazyk
L = {w ∈ {0, . . . , 9}∗
, w je zápis přirozených čísel dělitelných 25}.
2