The solutions that you submit should be your own You may not

The solutions that you submit should be your own.
You may not use solutions obtained from other students, from the web, or from other sources.
Do not wait until the night before this assignment is due to begin the assignment.


1. Give a CFG that generates the language L={0ⁱ10 | i 0 }. Also, demonstrate that your CFG generates the string 0010 by generating it from your CFG.

2. Give a CFG that generates the language L={aⁱbaⁱ | i 0 } {b^k | k 0 }. Also, demonstrate that your CFG generates the string aabaa by generating it from your CFG.

Solution

G = (V, , R, S) with set of variables V = {S, X}, where S is the start variable; set of terminals = {0, 1}; and rules S X1X1X1X X 0X | 1X |

Let A3 = A1 A2, and we need to show that L(G3) = A3. To do this, we need to prove that L(G3) A3 and A3 L(G3). To show that L(G3) A3, first consider any string w L(G3). Since w L(G3), we have that S3 w. Since the only rules in R3 with S3 on the left side are S3 S1 | S2, we must have that S3 S1 w or S3 S2 w. Suppose first that S3 S1 w. Since S1 V1 and we assumed that V1 V2 = , the derivation S1 w must only use variables in V1 and rules in R1, which implies that w A1. Similarly, if S3 S2 w, then we must have that w A2. Thus, w A3 = A1 A2, so L(G3) A3. To show that A3 L(G3), first suppose that w A3. This implies w A1 or w A2. If w A1, then S1 w. But then S3 S1 w,