Can't write context free grammar for language $L=\{a^n\#a^{n+2m}, n,m \geq 1\}$

Question

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!

Answer 1

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} $$

Answer 2

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

Answer 3

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.