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

  • 1
    $\begingroup$ What did you try? $\endgroup$ – Maharaj Jul 2 '16 at 12:22
  • $\begingroup$ S -> a S a | b S b | c S c | epsilon | a | b | c $\endgroup$ – Regularity Jul 2 '16 at 12:47
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 2 '16 at 13:07
  • $\begingroup$ 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. $\endgroup$ – Regularity Jul 2 '16 at 13:18
  • $\begingroup$ 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 $\endgroup$ – Regularity Jul 2 '16 at 13:26

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


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.