Chomsky hierarchy-Work Sheet

 

Kumaraguru College of Technology, Coimbatore

Department of Computer Science and Engineering

U18CST4003 – Theory of Computation

Chomsky Hierarchy of languages

Work Sheet 1.1

 

Given the following, identify the grammar types

a.    bAa → aa  

S → s  

Type 0 Grammar

b.    S → AT  

T → xy  

A → a  

Type 2 grammar

c.     A → aBb  

A → b  

B → a  

Type 2 grammar

d.    S –> ab

Type 2 grammar

e.     S –> AB
AB –> abc
B –> b

Type 1 grammar

f.     Sab –> ba
A –> S

Type 0 Grammar

Note: 

We say that a grammar belong to a particular type of grammar when all its productions belongs to that type.