Unrestricted Grammer

A grammer is called un restricted if all the production are of the form u--->v where u is in (v ∪ T)+

                     v is in (v ∪ T)*

v is a varible  and T is a terminal

 

Example: what language does the fiolloing unrestricted grammer derive.

S--->S1B
S1--->aS1b
bB--->bbbB
aS1b--->aa
B--->λ

Sol: S--->S1B
S--->aS1bB
S--->aaB
S--->aa

S--->S1B
S--->aS1bB
S--->aS1bbbB
S--->aabbbB
S--->aabbb

L={ an+1bn+k ,n>=1 k=-1,1,3,5.......}

0Comment