Question

Ex#3: Give a string of lengths, 4, 6, 8 generated by the following grammar G = (V, T, S. P).
S → 0S
S --> 0S1S
S --> λ

Answer 1

Answer: String length String 4 0000 6 000000 8 00000000

Explanation: Given production rules. S → 0S S --> 0S1S S --> λ String derivation: 4 lenght string: 0000 Step1: S → 0S Step2: substitute 0S in S, S → 00S , [Since S --> 0S] Step3: substitute 0S in S, S → 000S , [Since S --> 0S] Step4: substitute 0S in S, S → 0000S , [Since S --> 0S] Step5: substitute λ in S, S → 0000 , [Since S --> λ, which is null string] So we can derive 0000 as 4 length string from the given rules. 6 lenght string: 000000 Step1: S → 0S Step2: substitute 0S in S, S → 00S , [Since S --> 0S] Step3: substitute 0S in S, S → 000S , [Since S --> 0S] Step4: substitute 0S in S, S → 0000S , [Since S --> 0S]   Step5: substitute 0S in S, S → 00000S , [Since S --> 0S]   Step6: substitute 0S in S, S → 000000S , [Since S --> 0S] Step7: substitute λ in S, S → 000000 , [Since S --> λ, which is null string] So we can derive 000000 as 6 length string from the given rules. 8 lenght string: 000000 Step1: S → 0S Step2: substitute 0S in S, S → 00S , [Since S --> 0S] Step3: substitute 0S in S, S → 000S , [Since S --> 0S] Step4: substitute 0S in S, S → 0000S , [Since S --> 0S]   Step5: substitute 0S in S, S → 00000S , [Since S --> 0S]   Step6: substitute 0S in S, S → 000000S , [Since S --> 0S]   Step7: substitute 0S in S, S → 0000000S , [Since S --> 0S]   Step8: substitute 0S in S, S → 00000000S , [Since S --> 0S] Step9: substitute λ in S, S → 00000000 , [Since S --> λ, which is null string] So we can derive 00000000 as 8 length string from the given rules.

***Please give Upvote ***