Page 1 of 1
Let L = {w € {a,b}* numu(a) = num,(6)} and let G = S + SS aSb | bsa | €. The notation numy(c) means the number of times
Posted: Sat May 14, 2022 7:37 pm
by answerhappygod
- Let L W A B Numu A Num 6 And Let G S Ss Asb Bsa The Notation Numy C Means The Number Of Times 1 (36.43 KiB) Viewed 44 times
Let L = {w € {a,b}* numu(a) = num,(6)} and let G = S + SS aSb | bsa | €. The notation numy(c) means the number of times character c appears in string w. (a) Prove that L(G) SL using induction on the number of derivation steps. (b) (bonus) Prove that L CLG) using induction on the length of the string. hint: Consider breaking the inductive case into 4 sub-cases based on the first and last letters in the string, i.e., w € {awıb, bwia, aw a, bw b}. Two of those cases are tricky (but essentially identical) and depend on carefully considering how the overall string relates to one of the grammar production rules (i.e., what must be true for the rule to be useful).