The Chomsky Hierarchy

The Chomsky Hierarchy: Type 3

S  → aA

A → bcA|bc

L= {a(bc) ⁿ          n>0 }

1- abc

2- abcbc

3- abcbcbc

4- abcbcbcbc

5- abcbcbcbcbc

 

The Chomsky Hierarchy: Type 2

 

S  → Aba

A → aA|B

B → b

L={(a^m baⁿb)   m=1,0                   n>0}

1- Aab

2- aAab

3- aaAab

4- aaBab

5- aabab

 

 

 

The Chomsky Hierarchy: Type 1

 

S → aAbc

aA → aAb

A → a

L={(aabⁿc)       n>0 }

1- aAbc

2- aAbbc

3- aAbbbc

4- aAbbbbc

5- aabbbbc

 

The Chomsky Hierarchy: Type 0

 

S → aAb

A → aAb

aAb → c

L={(aⁿcbⁿ)                          n>1 }

1- aAb

2- aaAbb

3- aaaAbbb

4- aaaaAbbbb

5- aaaacbbbb