Page 1 of 1
- Let L = {w E {a,b}* | numw(a) = numw(b)} and let G = S + SS | aSb | 6Sa | €. The notation numw (c) means the number of
Posted: Thu May 12, 2022 8:44 am
by answerhappygod
- Let L W E A B Numw A Numw B And Let G S Ss Asb 6sa The Notation Numw C Means The Number Of 1 (256.32 KiB) Viewed 22 times
- Let L = {w E {a,b}* | numw(a) = numw(b)} and let G = S + SS | aSb | 6Sa | €. The notation numw (c) means the number of times character c appears in string w. (a) Prove that L(G) CL using induction on the number of derivation steps. (b) (bonus) Prove that L CL(G) 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 E {awıb, bwia, awia, bw1b}. 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).