What wiil be grammar rules for the language L={a^n b^n c^n d^n; n>0}


1 Answer 1


May I propose the following indexed grammar $G= ( \{S,A,C\}, \{a,b,c,d\}, \{f\}, S )$:

  • $S[\sigma] \to S[f\sigma]$

  • $S[\sigma] \to A[\sigma]\, C[\sigma]$

  • $A[f\sigma] \to a\, A[\sigma]\, b$, $\quad A[\,] \to \varepsilon$

  • $C[f\sigma] \to c\, C[\sigma]\, d$, $\quad C[\,] \to \varepsilon$

  • $\begingroup$ How can I turn it into Context sensitive grammar? $\endgroup$
    – Sasffef
    Commented Apr 9, 2022 at 17:18
  • 1
    $\begingroup$ Writing a context-sensitive grammar better be done directly. The method might be borrowed from the grammar for $\{ ww \mid w\in \{a,b\}^* \}$. I quote: "try to think of using a [grammar for $a^nb^n$] twice, one for the left and one for the right half. All you have to ensure that both grammars derive 'in sync'. This can be done by swapping around a control token." $\endgroup$ Commented Apr 9, 2022 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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