Consider the grammar G = (NT, Sig, R, S) where NT = {S, T}, Sig = {0, 1}, and th
ID: 3765859 • Letter: C
Question
Consider the grammar G = (NT, Sig, R, S) where NT = {S, T}, Sig = {0, 1}, and the rules in R are as follows:
1) S -> 1S1
2) S -> 0T
3) T -> 1T1
4) T -> 0
Prove that L(G) = LA = {1i 01j 01i+j | i, j 0} in two parts:
1) Using induction on the length k of a derivation, prove that every sentential form derived from the start symbol has one of four forms, depending on which rule was applied as the last step in the derivation.
last rule applied sentential form
1) S -> 1S1 1k S1k for k 0
2) S -> 0T 1k-1 0T1k-1 for k 1
3) T -> 1T1 1k-j-1 01j T1j1k-j-1 for k 1 and for some j 0
4) T -> 0 1k-j-2 01j 01j1k-j-2 for k 2 and for some j 0
2) Prove that the language of grammar G is LA as specified above. Show that start symbol S derives terminal string w if and only if w belongs to LA.
Explanation / Answer
1) (i) For the sentential form 1k S1k for k >=0 ,
as per induction rule k=0, the derived string is S , for k=1, derived string is 1 S 1 and When k=n, the derived string is 1nS1n. therefore derivation Rule 1 (i.e S-> 1 S 1) is applied.
(ii) For the sentential form 1k-1 0T 1k-1 for k >=1,
as per induction rule k=1, the derived string is 0T , for k=2, derived string is 1 0T 1 and When k=n, the derived string is 1n0T1n. therefore derivation Rule 1 (i.e S-> 1 S 1) and Rule 2 (i.e, S->0T) are applied.
(iii) For the sentential form 1k-j-1 01jT1j 1k-j-1 for k >=1, j>=0,
as per induction rule k=1,j=0 the derived string is 0T , for k=2,j=1 derived string is 01T1 and
When k=n, j=n-1 the derived string is 01n-1T1n-1. therefore derivation Rule 2 (i.e S-> 0T) and Rule 3 (i.e, T->1T1) are applied.
(iv) For the sentential form 1k-j-2 01j01j 1k-j-2 for k >=2, j>=0,
as per induction rule k=2,j=0 the derived string is 00 , for k=3,j=1 derived string is 0101 therefore derivation Rule 2 (i.e S-> 0T) and Rule 3 (i.e, T->1T1) and Rule 4 (i.e, T-> 0) are applied.
2)
S=> 1 S 1
11 S 11
11 0 T 11
1 1 0 1 T 1 11
1 1 0 1 1 T 1 1 1 1
1 1 0 1 1 1 T 1 1 1 1 1
w= 1 1 0 1 1 1 0 1 1 1 1 1 => (12 0 13 0 15)
w belongs to LA. Hence proved.