Building Grammer for a given Language Building Grammer for a given Language
CSC360- Tutorial
Gur Saran Adhar

A grammer generating {0i1j2k | i = j or j = k }

1. S Þ AB | CD
2. A Þ 0A1 | L
3. C Þ 0C | L
4. B Þ 2B | L
5. D Þ 1D2 | L

Discussion: The two cases i = j, j = k are set apart by the two options in production 1. Repeated application of production 2 provides equal number of 0 and 1 (the case when i = j). Similarly repeated application of production 5 provides equal number of 1 and 2 (the case when j = k). Production 2 along with production 4 produce the strings

0i1i2k
and production 5 along with production 3 produce the strings
0i1j2j


File translated from TEX by TTH, version 2.25.
On 16 Sep 1999, 08:39.