Give a context-free grammar (look up the definition if necessary) that generates

Question

Give a context-free grammar (look up the definition if necessary) that generates the language of balanced parentheses and prove that your grammar is correct according to the definition of a balanced string of parentheses given below:

Let the Pcount (i.e. parenthesis count) of a string of left and right parentheses be defined by:

1. The Pcount of the empty string is 0.

2. Pcount[ x( ] = Pcount[ x ] + 1

3. Pcount[ x) ] = Pcount[ x ] 1

Then, a string of left and right parentheses is balanced if its Pcount is 0, and no prefix of the string has a negative Pcount.

You will have to prove that every terminal string generated by your grammar is balanced and conversely that every balanced string is generated by your grammar.

Explanation / Answer

Context Free grammer:
S->(S)|SS|0S|0

Language generated by the given grammer contains only parenthesis and digit 0.

To prove: Every terminal string generated by grammar is balanced .

As it is clear from the grammer that string generated from the grammer always contains wither no parenthesis or balanced parenthesis. Every time when we generate a string with the above grammer it puts balanced parenthesis around it. So every time it generates balanced terminal string.

To prove: Every balanced string is generated by grammar.

So four cases are possible:

case 1:(000) this can behandled using S->(S) as many times as number of pairs of parenthesis and then using S->0S to generate all the 0's in the string.

case 2:(((0))) this can be handled using S->(S) as many times as number of pairs of parenthesis and then using S->0 .

case 3:(0(0)) this can be handled using S->(S) followed by S->0S,followed by S->(S), followed by S->0 .

case 4:(0)(0) and this can be handled using S->SS, followed by S->(S), followed by S->0 and similarly for other S.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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