1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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?) $\endgroup$
    – rici
    Oct 6 '17 at 4:24
  • 2
    $\begingroup$ 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! $\endgroup$
    – Dandelion
    Oct 6 '17 at 6:29
  • $\begingroup$ And once you have a guess, you try and prove it correct. $\endgroup$
    – Raphael ♦
    Oct 7 '17 at 13:01
1
$\begingroup$

Structural induction would prove the following:

  • 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.

Presumably the reverse is also true, but I'll leave such pondering for you.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.