Odstranění ε-pravidel – příklady k procvičení
Příklad 1.
Je dána bezkontextová gramatika G = ({S, A, B, C, D}, {b, c}, P, S), kde množina pravidel
P = {S → ABC
A → Ab | BC
B → bB | b | Ab | ε
C → cD | c | Ac | ε
D → SSS | cSAc}
Vytvořte ekvivalentní gramatiku G bez ε-pravidel.
Příklad 2.
Je dána bezkontextová gramatika G = ({S, X, Y, Z}, {0, 1}, P, S), kde množina pravidel
P = {S → 1X | Y 1 | XZ
X → 0Y Z1 | S1X | Y
Y → 1 | X1 | ε
Z → SZ | 0 | ε}
Vytvořte ekvivalentní gramatiku G bez ε-pravidel.
Příklad 3.
Je dána bezkontextová gramatika G = ({A, B, C}, {a, b, c}, P, S), kde množina pravidel
P = {A → BC | a | ε
B → aB | ACC | b
C → cC | AA | c}
Vytvořte ekvivalentní gramatiku G bez ε-pravidel.
1