Palindromes with 2 symbols and $3|l(u)$

Question

The following grammar generates palindromes with $2$ symbols. $$G=\{\{S\}, \{a,b\}, \{S\rightarrow\epsilon|a|b|aa|bb|aSa|bSb\}, S\}$$

So if I'm right, each $u$ in the language $L$ generated by $G$ is a palindrome. Also,

$$S\rightarrow aXa|bXb$$ $$X\rightarrow a|b$$

generates a language, where $l(u)$ for each $u\in L$, $l(u)=3$. But how to define a grammar for the language, where each word has a length which is a multiple of $3$, and a palindrome as well? What is the basic idea to do this?

Answer 1

Okay, so I orginally answered the wrong question, here is my attempt at the real one:

---

We want to find a grammar for the language $L = \{w ∈ Σ^*;\; \text{$w = \overleftarrow{w}$ and $3|l(w)$}\}$, where $Σ = \{a,b\}$. That’ll do: \begin{align} S →&aaaSaaa|aabSbaa|abaSaba|abbSbba \\ |& baaSaab|babSbab|bbaSabb|bbbSbbb \\ |& aaa | bab | aba | bbb | ε \end{align} The idea behind this is that any word $w ∈ Σ^*$ is in $L$ if and only if it is either

• a palindrome of length $0$ or $3$, or
• consisting of an smaller palindrome $S$ whose length is divisible by $3$ with a three letter word $w$ and its reflection $\overleftarrow{w}$ attatched to its beginning and end respectively, i.e. $wS\overleftarrow{w}$.

Both condititions then need to be “hard-coded” for the alphabet $Σ$.