I am trying to design a context-free grammar for the language of bit-strings wit

Question

I am trying to design a context-free grammar for the language of bit-strings with an equal number of 0's as 1's. I have devised the following grammar: S rightarrow epsilon S rightarrow 1S0 S rightarrow 0S1 This grammar does indeed only generate strings with an equal number of 0's as 1's. However, it does NOT generate ALL such strings. Give an example of such a string (one with an equal number of 0's as l's, but cannot be produced by the given grammar). Fix it -- i.e., devise a grammar which: Only generates strings with an equal number of 0's as 1's Generates all such strings.

Explanation / Answer

A)

If we start the grammar with S -> 1S0, then no matter in what way the S in the middle is substituted, it will always end with 0. Similar if we start the grammar with S -> 0S1, then no matter in what way the S in the middle is substituted, it will always end with 1.

The language this grammar generates has equal number of 0’s and 1’s however it always starts and ends up with different symbols.

Hence, any string which starts and ends with the same symbol (and has equal number of 1's and 0's) can be given as an example of contradiction.

Examples are 1001, 0110, etc.

------------------------------------------------------------------------------------------------------------------

B)

To fix it add a grammar rule S -> SS to the grammar. This ensures that strings which start and end with same symbol and have equal number of 1’s and 0’s are also generated.

Complete grammar is the following:

S -> e

S -> SS

S -> 1S0

S -> 0S1

If you have any queries regarding any of the above, please ask in the comments and I will make sure to help you with it.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.