What strings does each grammar produce? Re-write each in Chomsky Normal Form.

1. S -> aA

A -> a | AA |

2. S -> ABCD

A -> aA | a

B -> bB | b

C -> c

D -> dD | d

3. What strings does the following accept? Rewrite it in modified Chomsky Normal Form:

S-> aaBccD |

B ->

D ->

4. Create a grammar that accepts only strings with an odd number of a’s. (It doesn’t have to be in Chomsky Normal Form.)

5. Create a grammar that accepts the empty string, and one or more "abcd"s. (So, "abcdabcd" and "abcdabcdabcd" are valid, but "abd" is not.)

It doesn't have to be in Chomsky Normal Form.