# Determining Language from Context Free Grammar

I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar:

$S \to 0B \mid 1A$

$A \to 0 \mid 0S \mid 1AA$

$B \to 1 \mid 1S \mid 0BB$

What this says to me is that the first symbol can be either a 0 or 1, and the next could be 0 or 1 or 1 or 0, and you continue down the parse tree from there. How does one determine what the language of the grammar is? I having trouble putting the patterns of symbols into a language definition.

• One thing you could try is to enumerate all the short sentences and see if some pattern jumps out at you. Even just counting the number of sentences of each length might give you a clue. (There are two sentences of length two and eight of length four. Can you see why odd-lengths are impossible? How many six-symbol sentences are there?)
– rici
Oct 6, 2017 at 4:24
• What do you mean by a language definition? This grammar is itself a way to define this language! Another way would be to use PDAs or turing machines machines or alternatively an algebraic formula to define this language! Oct 6, 2017 at 6:29
• And once you have a guess, you try and prove it correct.
– Raphael
Oct 7, 2017 at 13:01

• All words generated from $S$ have the same number of 0s and 1s.
• All words generated from $A$ have an excess of one 0.
• All words generated from $B$ have an excess of one 1.