0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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$
    – Hendrik Jan
    Apr 22 at 23:09
  • $\begingroup$ Thank you for your help! $\endgroup$
    – MWR_
    Apr 23 at 12:27

0

Reset to default

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.