Unrestricted Grammar: Example
G = (N, T, P, S), where N = {S, A, B}, T = {a}
P = { 1: S ® ASB, 2: S ® a,
3: Aa ® aaA, 4: AB ® e       }
S Þ a       [2]
S Þ ASB [1] Þ AaB [2] Þ aaAB [3] Þ aa [4]
Textové pole: …
…
S Þ ASB [1] Þ AASBB [1] Þ AAaBB [2] Þ
        AaaABB [3] Þ aaAaABB [3] Þ
        aaaaAABB [3] Þ aaaaAB [4] Þ aaaa [4]
Note: L(G) = {a2n: n ³ 0}
28/45