CODEWITHSUNDEEP
theorycontext-free-grammarautomata
anaon12
anaon12

Reputation: 27

How can we prove this using proof by induction?

Let G be the following grammar:

S → T⊣

T → TaTb | TbTa | ε

Show that L(G) = {w⊣| w contains equal numbers of a’s and b’s} using proof by induction on the length of w.

What can be assumed in this situation?

Upvotes: 1

Views: 643

Answers (1)

Hassan Abbasi
Hassan Abbasi

Reputation: 272

For simplicity we can ignore S symbol and just prove that T produces equal number of a's and b's.

Assuming L={w| w contains equal numbers of a’s and b’s}, the proof is comprised of two parts: 1-Every string with length n that T produces, is in L. 2-Every string in L with length n can be produced by T.

1) The proof of 1 is simple by induction. The rule (T → ε) produces equal No. of a's and b's, and by induction the rules T → TaTb | TbTa also keeps a's and b's equal.

2) We assert that every string in L with length n which ends with b, can be produced by first using the rule T → TaTb. The proof can be established by numbering the letters. we give each 'a' +1 and each 'b' -1. Every string in L has total rank of '0' (due to equal No of a's and b's). Every string in L ending with b, starts with rank 0 and reaches rank +1 just before last b. It may reaches rank 0 again in between before seeing an 'a'. This is where we can rewrite the string w as T1aT2b in which T1 and T2 are in L too and by induction can be produced by T.(If the rank of w never reaches 0 in between it means that w starts with a, so T1=ε) The proof for strings ending with 'a' is similar.

Upvotes: 2

Related Questions