context free grammar issue [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I need help with my context-free grammar for this language:

{b^4 n^m bd^n n^3n+m | m,n >= 0}

So far I got this:

S-> bbbbXbY
X-> n | E
Y-> dYnnnX

Answer 1

Assuming S is start symbol, E is empty word (𝜀), your language is {b^4 n^r b d^s n^(3s+r) | r,s ≥ 0}.

The correct grammar

S → bbbbN
N → bD | nNn
D → dDnnn | 𝜀

Explanation

• S generates b^4 on the left and switches to N. It never occurs in the derivation again.
• N generates n^r on both sides, then b in the middle and switches to D. After that it never occurs in the derivation again.
• Finally D generates d^s n^(3s) and finishes the derivation.

S                               (start symbol)
→ b^4 N                         (applied S → bbbbN)
→ b^4 n^r N n^r                 (applied N → nNn r-times)
→ b^4 n^r bD n^r                (applied N → bD)
→ b^4 n^r b d^s D (nnn)^s n^r   (applied D → dDnnn s-times)
→ b^4 n^r b d^s (nnn)^s n^r     (applied D → 𝜀)

Mistakes in the original grammar

Your grammar generates empty language, because Y will always be present in the product of each derivation step (infinite recursion). There is also a fundamental problem with context: the first sequence of ns is generated by X from S → bbbbXbY independently of the second one generated by Xs from Y → dYnnnX. If you add Y → 𝜀, the language will be {b^4 n^r b d^s n^(3s+t)}. And the grammar will be ambiguous, as bbbbXbddYnnnXnnnX can be generated (using Y → dYnnnX twice) and the final sequence of ns can be usually generated in many ways.

Steps to fix the original grammar

• Add Y → 𝜀 to stop infinite recursion.
• Move X from the end of Y → dYnnnX to the end of S → bbbbXbY to get rid of ambiguity.
• Chain the Xs in newly created S → bbbbXbYX together to force the context. The same amount of ns must be generated by both of them.

Now you have the correct grammar at the top of this answer.