Klasy Gramatyk 2

Gramatyka kontekstowa

G₂ = ({S. B. C}. {a. b. c}. P. S )

P: S -> aSBC | abc cB —» BC bB -> bb bC —> bc

cC -> cc

L(G₂) = { abc, aabbcc, aaabbbccc, ...} = {aⁿbⁿcⁿ, n £ 1}

S -> abC -> abc

S -> aSBC -> aabCBC -> aabcBC -> aabBCC -» aabbCC -> aabbcC -> aabbcc

S -> aSBC -> aaSBCBCBC ->aaabCBCBC -> aaabcBCBC -> aaabBCCBC -> aaabbCCBC -> aaabbcCBC -> aaabbccBC -> aaabbcBCC aaabbBCCC -> aaabbbCCC -> aaabbbcCC -> aaabbbccC -> aaabbbccc

Giamatyka be z kontekstowa

G₃ = ({S,A}, {0,1}, P, S )

P: S -> ASA A —> 1 S->0

L(G₃) = { o. 101.11011. ...}= {1ⁿ01ⁿ. n ^ 0}

s->o

S-> ASA—> 1SA—> 10A —> 101

S —> ASA —> 1 SA —> 1ASAA —> 11SAA —> 110AA —> 1101A —> 11011 Gramatyka kontekstowa

G₄=({S,A},{0,1,M.P₁S)

P: S -> 0A1 OA —»00A1

A —> ^

L(G₄) = {01,0011,000111    = {0ⁿ1ⁿ,    1}

S -> 0A1 -> 01

S —> 0A1 —> 00A11 ->0011

S —> 0A1 —> 00A11 -> 000A111 -> 000111