# Find a CFG for palindromes with at most three c's

I'm trying to figure this one out, as I've found the CFG for the palindrome language. I can't work on a solution that also covers #c(w) <= 3.

Find a CFG for the language {w∈{a,b,c} | Reverse(w)=w, #c(w)<=3}?

Would appreciate your help

• What did you try? – Maharaj Jul 2 '16 at 12:22
• S -> a S a | b S b | c S c | epsilon | a | b | c – Regularity Jul 2 '16 at 12:47
• What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help. – David Richerby Jul 2 '16 at 13:07
• Hi, this is not a home-work question but rather I'm preparing for an exam. I'm familiar with CFG but can't understand how to unify the CFG for palindrome and the condition about the amount of c's in w. – Regularity Jul 2 '16 at 13:18
• Here is something I came up to guarantee that the amount of A's is bigger than 3. but I'm struggling with lower or equals to: S-> aXa | bSb | cSc X-> aYa | bXb | cXc | a Y-> aYa | bXb | cYc | epsilon | a | b | c – Regularity Jul 2 '16 at 13:26

## 1 Answer

Call $$P=\{w\in\{a,b,c\}^*\mid w=w^R\}$$ the palindrome language and $$Q=\{w\in\{a,b,c\}^*\mid |w|_c\le 3\}$$ the language of strings having at most 3 $c$'s. Then your language is $L=P\cap Q$ and so is a CFL, since we know the intersection of a CFL (which $P$ is) and a regular language (which $Q$ is) is a CFL. With that out of the way, let's get a CFG for $L$.

You know that a grammar for $P$ can be given by the productions $$S\rightarrow aSa\mid bSb\mid cSc\mid a\mid b\mid c\mid\epsilon$$ Now let's modify this grammar so that it generates palindromes with at most 3 $c$'s. The production $S\rightarrow cSc$ will add two $c$'s to the string being generated, so we want to limit ourself to subsequent productions that generate at most one more $c$. We can do that by changing $S\rightarrow cSc$ to $S\rightarrow cTc$ and forcing $T$ to generate palindromes with at most one $c$. This is simple enough: we can add these productions, $$T\rightarrow aTa\mid bTb\mid a\mid b\mid c\mid \epsilon$$ So finally we have the grammar $$\begin{eqnarray} S&\rightarrow& aSa\mid bSb\mid cTc\mid a\mid b\mid c\mid\epsilon \\ T&\rightarrow& aTa\mid bTb\mid a\mid b\mid c\mid \epsilon \end{eqnarray}$$