I have a language where each string in the language has even amount of 0's as 1's (eg. 0101, 1010, 1100, 0011, 10 are all in the language). I was hoping to define a context-free grammar that describes this language. After defining a context-free grammar I want to formally prove that this context-free grammar describes this language.
I've came up with the context-free grammar production rules:
S->0S1S
S->1S0S
S->ε
Is this the correct context free grammar to define this language?
Im kind of stumped for the proving part. I'm guessing I will need some sort of induction?
This grammar looks correct to me.
I would prove it by showing both directions (i.e. a string is in the language iff it's produced by the grammar).
Proving that all strings produced by the grammar are in the language is easy: Simply consider that all productions of the grammar output the same number of 1s and 0s. Therefore any combination of productions must produce a string in the language.
To prove that all strings in the language can be produced by the grammar seems more tricky. I think induction could work on this, but nothing obvious comes to mind.
Good luck