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.

Comments

Post a Comment

Popular posts from this blog

Chomsky Hierarchy of languages

Image
 Chomsky classified the grammars into four types. They are Type-0, Type-1, Type-2 and Type-3. This is shown in the following diagram The description of these grammars are given in the following section 1. Type-0 Grammar Type-0 grammars represents exactly the languages recognized by the Turing Machine. This is also called as unrestricted or phrase-structured grammar. The general structure of this grammar is given below, where both the left and right hand side of the production may contain any number of terminals and variables. Example 1.1:  S -> ACaB                               Bc -> acB                               CB -> DB                                aD -> Db 2. Type-1 Grammar Type-1 grammars ...
Read more