Domácí úkol, příklad 2, přejmenování neterminálů:

N[00] → aN[10] | bN[01]

N[10] → aN[00] | bN[11]

N[01] → aN[11] | bN[00]

N[11] → aN[01] | bN[10] |

Domácí úkol, příklad 3b:

G = ({N[0], N[1], N[2]}, {a, b, c}, P, N[0]),

P:

N[0] → aN[1] | bN[1] | cN[1]

N[1] → aN[2] | bN[2] | cN[2]

N[2] → aN[0] | bN[0] | cN[0] |

Množina pravidel upravená tak, aby splňovala podmínky regulární gramatiky

N[0] → aN[1] | bN[1] | cN[1]

N[1] → aN[2] | bN[2] | cN[2] | a | b | c

N[2] → aN[0] | bN[0] | cN[0]

Původní gramatika: uN[1] => uaN[2] => ua, kde u je terminální řetězec

Upravená gramatika: uN[1] => ua pomocí N[1] → a

Bezkontextová gramatika pro jazyk

P:

S →  | ab | aAb

A → ab | aAb

Cvičení 2b, příklad 4

G = ({S‘, S, N[c], N[ca], N[cac]}, {a, b, c}, P, S‘)

P:

S‘ →  |  aS | bS | cN[c] | a | b | c                           Tato pravidla jsou navíc kvůli
možnosti generování
S → aS | bS | cN[c] | a | b | c
N[c] → aN[ca] | bS | cN[c] | a | b | c
N[ca] → aS | bS | cN[cac] | a | b
N[cac] → aN[cac] | bN[cac] | cN[cac]

Druhá možnost: odstranit pravidlo N[ca] → cN[cac] a s ním i všechna pravidla pro neterminál N[cac]