Defining a context-free grammar for a specific language

0
votes

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?

1
parsingcontext-free-grammarcomputation-theorycontext-free-language
This question appears to be off-topic because it would be a better fit on the Computational Science site. – halfer
Computational science is the application of numerical techniques and heavy-duty computation to solve scientific problems. This problem is computer science, not computational science. – user2357112 supports Monica

1 Answers

0
votes

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