Solutions to Assignment 4 - Computer Science

5. Here is a context-free grammar for L= fwjwcontains more 1’s than 0’sg: S ! TSj1Tj1S T ! TTj0T1 j1T0 j Note that Tgenerates all words in which there are equal number of 1’s and 0’s. If a word w contains more 1’s that 0’s, then wmust be of one of the following forms. w= 1w 1 such that w 1 contains more 1’s than 0’s. w= 1w 1 ... ................
................