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

1. S -> aA

A -> a | AA |

one or more a’s

S-> XA

S -> a

X-> a

A -> a | AA

2. S -> ABCD

A -> aA | a

B -> bB | b

C -> c

D -> dD | d

one or more a’s, followed by one or more b’s, followed by c, followed by one or more d’s

S -> LC

L -> AB

A -> MA | a

M -> a

B -> NB | b

N -> b

C -> c

D -> OD | d

O -> d

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

S-> aaBccD |

B ->

D ->

aacc and empty string

S’ -> LX

S’ ->

S -> LX

L -> MN

M -> a

N -> a

X -> YZ

Y -> c

Z -> c

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.)

S -> aA

A -> aB |

B -> aA

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.

S ->

S -> abcdS