Proving that G matches L: [.5pts per prompt = 5pts]

Finish the Inductive Proof L = {w | w has an equal number of as and bs}

// we have 3 non-terminals

1 S -> aB // starts with a

2 S -> bA // starts with b

// comes to A after starting with b. A means balance that b with a.

3 A -> a

4 A -> aS

5 A -> bAA

// comes to B after starting with a. B means balance that a with b.

6 B -> b

7 B -> bS

8 B -> aBB

We were doing induction to prove that G can generate all strings of L.

GIVEN ASSUMPTIONS when |w| <= k-1

T1. S can =*=> w if w consists of an equal number of a's and b's

T2. A can =*=> w if w has one more a than b's

T3. B can =*=> w if w has one more b than a`s

You must now prove the properties (T2 and T3) of A and B

for the |w| = k step.

Please fill in the template below. For Why questions, refer to the above given assumptions. E.g. Using the given assumption T1.

T2 step for A:

Prove that if w has one more a than b's, A can =*=> w where |w| = k

(describe w in terms of shorter strings z, y1 and y2)

w looks like: a< z > or b [.5]

Thus z and y1 and y2 have properties such that:

z:

each y1 and y2:

What non-terminal can derive z? ??

Why???

What non-terminal can derive each y???

Why???

Thus A =*=> w:

Starting with these rules from A: **

T3 step for B:

Prove that if w has one more b than a's, B can =*=> w where |w| = k

Has to be done for the proof to be complete. But it is not required for this HW.