Fix the alphabet = {0, 1}. Define a substring of w to be any string x such that w = uxv for some u, v . Now consider the language A = {w | 001 is not a substring of w} For example, , 01, 1111, 10101, and 0111010101 are in A, but 10001 and 11001011 are not.

Consider the context-free grammar G = ({S}, , R, S), where the rules R are:

S

| S 0

| 1 S

| 0 1 S

Show that L(G) = A.