Theory of Computing G = E = {a,b}

// we have 3 non-terminals S, A, B

1 S -> A B

2 A -> a A

3 A -> a

4 B -> b B

5 B -> b

L = {a^n b^m | n and m > = 1 }

Prove that L == L(G).

First we list what we need to prove for each non-terminal in the grammar.

What to prove:

T1. If w = a^n b^m, S =*=> w

T2. If w = a^n , A =*=> w

T3. If w = b^m , B =*=> w

For all w in L, show that the non-terminal can derive it.

Basis: if |w| = 1, what are the strings in the respective languages?

T1. There is no length 1 string in L

T2. w = a

YES A =*=> a by P3.

T3. w = b

YES B =*=> b by P5.

if |w| = 2,

T1. w = ab

YES S => AB =*=> ab because of T2 and T3 above.

Therefore, S, A, and B can generate the shortest strings of their respective languages.

Assumptions: Assume 3 properties T1, T2 and T3 are true for |w| <= k.

Assumption 1 is for S

For length k or less, S derives all a^n b^m where n+m =< k

Assumption 2 is for A

For length k or less, A derives all a^n where n <= k

Assumption 3 is for B

For length k or less, B derives all b^m where m <= k

Therefore, S, A and B can generate the length k strings of their respective languages.

Step: For length |w| = k+1 strings of respective languages, express them in terms of shorter strings

covered by the assumptions.

T1:

If |w| = k+1

Then, w = y z y is made up of all as and z is made up of all bs

|z| <= k |y| <= k

Assumption 2 and 3 says y and z can be derived from A and B

Thus, S =rule1=> AB =*=> y z

T2:

If |w| = k+1

Then w = a y y is made up of ____________

{y| = ___________

Assumption ____ says y can de derived from ______

A =__________________ => a y

T3:

If |w| = k+1

Then w = b z z is made up of ___________

|z| = _______________

Assumption ___________ says z can be derived from __________________

B =________________ => b z

Conclusion: Since the shortest strings can be derived from each non-terminal and it works for all longer strings, each non-terminal can derive the respective language.