Consider the grammar over the alphabet { 0, 1 } as follows S -> 0 X Y 1 X -> 0 0
ID: 3577486 • Letter: C
Question
Consider the grammar over the alphabet { 0, 1 } as follows S -> 0 X Y 1 X -> 0 0 X X -> e Y -> Y 1 1 Y -> e
a) Describe in English what the strings generated by this grammar look like. Be as specific as you can. Show the derivation of the string '000111'.
b) Modify the grammar so that it also allows additional strings where the zeros and ones are reversed. For example if the original grammar generates '000111' the modified grammar should generate '000111' and also '111000'. This behavior should hold true for every possible string generated by the original grammar.
Explanation / Answer
Given the grammer S -> 0 X Y 1 , X -> 0 0 X , X -> , Y -> Y 1 1 , Y ->
1. S -> 0 X Y 1
Apply X—> and Y—> we get S—>01
2. S -> 0 X Y 1 (Answer to Point a )
Apply X—>00X and Y—>Y11 we get S—>000XY111 , then again
Apply X—> and Y—> we get S—>000111
3. S -> 0 X Y 1
Apply X—>00X and Y—>Y11 on S -> 0 X Y 1 , we get S—>000XY111 , then again
Apply X—>00X and Y—>Y11 on S—>000XY111, we get S—>00000XY11111 , then again
Apply X—> and Y—> on S—>00000XY11111 we get S—>0000011111
So we can see Strings generated are { 01 , 000111 , 0000011111, … .. . . }
English : There are equal number of 0s and 1s , with Odd number of 0 and 1s and 0s must precede 1s.
b) Modified Grammar should generate both Strings as 000111 as well as 111000
Modified Grammar is as follows (Newly added are Highlighted in bold)
S -> 0 X Y 1 , S—> 1XY0
X -> 0 0 X , X—> 11X
X ->
Y -> Y 1 1 , Y —>Y00
Y ->
lets Take an Example and see why It works (Modified grammar )
S -> 1 X Y 0
Apply X—>11X and Y—>Y00 on S -> 1 X Y 0 , we get S—>111XY000 , then again
Apply X—> and Y—> on S—>111XY000 we get S—>111000 AND
S -> 0 X Y 1
Apply X—>00X and Y—>Y11 we get S—>000XY111 , then again
Apply X—> and Y—> we get S—>000111
So Modified grammar generates both 000111 as well as 111000.
Thanks, I hope it clarifies. Let me know if there and is any concern and please provide feedback