I've been trying to come up with a proper grammar for this sort of language:

L = { aˣbʸaˣbʸ | x, y >= 0 }

I have failed to find a way to enforce consistent generation of terminals on either part (the same amount of a's and b's on both "sides", where a side would be aˣbʸ).

I've observed that this language could be a concatenation of two languages, where each language is a "side". But I'm not sure how I can use that information.

I think you can only devise at least type 1 grammars for this, because of the Pumping lemma, but I'm not sure.

I'm currently a beginner in Formal Language Theory, just getting started, so sorry if I'm a bit dense for now.

  • $\begingroup$ Indeed, this language is not context-free. Wikipedia has a non-contracting grammar for this language: en.wikipedia.org/wiki/Context-sensitive_grammar#ambncmdn . Non-contracting grammars are easier to design than context-sensitive grammars, although they have the same power. $\endgroup$ Apr 22 at 23:09
  • $\begingroup$ Thank you for your help! $\endgroup$
    – MWR_
    Apr 23 at 12:27


Your Answer

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