Spent some time on this problem and seems like I am not able write context free grammar for language

$L=\{a^n\#a^{n+2m}, n\geq 1\wedge m \geq 1, n\in \mathbb{N} \wedge m\in\mathbb{N}\}$

I am sure I am missing something obvious, but can't figure out what.

I understand that strings are in L:

for odd n

1 # 3, 5, 7, 9, ...

3 # 5, 7, 9, 11, ...

5 # 7, 9, 11, 13, ...

i.e. one t followed by # followed by 3 or 5 or ... t's; three t's followed by 5 or 7 or 9 t's ...

for even n

2 # 4, 6, 8, 10, ...

4 # 6, 8, 10, 12, ...

6 # 8, 10, 12, 14, ...

i.e. two t's followed by 4 or 6 or 8 ... t's and so on.

I am struggling to generate rules. I understand what I can start with one or two t's then followed by # then followed by 3 or 4 t's.

What I can't figure out how to recursively manage n increment, i.e. to make sure for example there are least 7 t's after 5 t's followed by #.

I also tried to check if L is CFL, but with no success :(

Any hints to the right direction, ideas and solutions are welcomed!


You can't directly relate the number of $a$'s before the $\#$ with the number of $a$'s after the $\#$; context-free grammars do not have a way to express such equations. Instead, focus on building the two strings of $a$'s together: whenever you add one on the left, add one on the right, and vice versa. Separately, you can add two $a$'s on the right simultaneously. However, you can't do both at the same time. You can either first build $a^n\#a^n$ and append $a^{2m}$, or build $a^n\#a^n$ and $a^{2m}$ separately and concatenate the two. (Building $a^{2m}$ and then incrementally prepending $a^n\#a^n$ won't work because you'd need to control the number of $a$'s in the middle).

Here is the concatenation-based approach. I urge you to work out the shorter but conceptually very slightly more complicated approach where you start with $S$, then build up $L$ without using another non-terminal.

$$ \begin{array}{rl} L \rightarrow & S \; T \\ S \rightarrow & a \# a \\ S \rightarrow & a S a \\ T \rightarrow & a a \\ T \rightarrow & T a a \\ \end{array} $$

  • $\begingroup$ Your grammar is slightly wrong, you allow $n = 0$. $\endgroup$ – sxd Nov 19 '11 at 21:54
  • $\begingroup$ @DimitriSurinx Isn't that supposed to be allowed? Oh, I see the question is ambiguous; I read it as $\{a^n\#a^{n+2m} \mid n\in\mathbb{N} \wedge m\in\mathbb{N} \wedge m\ge1\}$, but your reading as $\{a^n\#a^{n+2m} \mid n\in\mathbb{N} \wedge m\in\mathbb{N} \wedge n\ge1 \wedge m\ge1\}$ also makes sense. Fortunately this isn't the sticky point. $\endgroup$ – Gilles Nov 19 '11 at 22:00
  • $\begingroup$ +1 (especially for the first sentence) and whole explanation in general! $\endgroup$ – Mr. L Nov 19 '11 at 22:00
  • $\begingroup$ @Gilles yes you are right it looks a bit ambiguous. Will edit my question. $\endgroup$ – Mr. L Nov 19 '11 at 22:03

The $a^n\#a^n$ part should be grown from the $\#$ outwards.

  • 2
    $\begingroup$ Accept and +1 for trying to make me think! $\endgroup$ – Mr. L Nov 19 '11 at 21:54

I think this is the solution:

$S \rightarrow aLaT$

$L \rightarrow aLa \mid \#$

$T \rightarrow Taa \mid aa$

This language is actually just $\{ a^n\#a^n \mid n \geq 1\} \circ (aa)^+$, where $\circ$ is the concatenation operator. Which is why this CFG is so easy to construct, as it is an easily expressible language followed by an arbitrary even number of a's.

  • $\begingroup$ it's easy indeed now I can see it. It seems like I overcomplicated a easy problem ( again ). +1 $\endgroup$ – Mr. L Nov 19 '11 at 21:53
  • $\begingroup$ @Liutauras, that happens to everyone! Once you get more familiar with context free grammars you will how you have to construct them. $\endgroup$ – sxd Nov 19 '11 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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