Redukované CFG – příklady k procvičení
Příklad 1.
Buď G = ({S, A, B, C, D, E}, {a, b, c}, P, S) CFG s pravidly
P = {S → ab | cCc
A → aEb | cBa
B → BbB | aAa
C → aSb | aaD
D → cCa | bb | ac
E → EE}
Nalezněte redukovanou bezkontextovou gramatiku G takovou, že L(G ) = L(G).
Příklad 2.
Je dána bezkontextová gramatika G = ({S, A, B, C, D, E}, {a, b}, P, S) s pravidly
P = {S → aa | bb
A → bB | aE
B → aC | bEa
C → bD | aaE
D → aSa | bSb | ε
E → bEb}
Nalezněte redukovanou bezkontextovou gramatiku G takovou, že L(G ) = L(G).
Příklad 3.
Buď G = ({S, A, B, C, D}, {a, b, c, d}, P, S) bezkontextová gramatika s pravidly
P = {S → ab | aDa
A → cd | AA
B → bBB | bS
C → CC
D → aC | ba}
Nalezněte redukovanou bezkontextovou gramatiku G takovou, že L(G ) = L(G).
1