# Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? $$\begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{equation}$$ The arrow over w means, that the word w is written backwards.

I already know that $$\begin{equation} \Sigma=\{a, b, c\} \end{equation}$$ and V (non terminal symbols) maybe have to be $$\begin{equation} V=\{S, A, B, C\} \end{equation}$$

Thank you for helping.

$$S \rightarrow ASA|BSB|ATA|BTB$$ $$T \rightarrow CAZC|CBZC$$ $$Z \rightarrow AZ|BZ|\epsilon$$ $$A \rightarrow a , B \rightarrow b, C \rightarrow c$$
First rule provides the $$w$$ and $$w^R$$ in the language, second rule makes sure $$v \ge 1$$ and has 1 c in both sides and third is just constructing the $$v$$ further. My assumption was your arrow on top of last $$w$$ was just meant it is reversed.
• I just use those arbitrary non-terminals to impose extra rules. Using "S" to impose the $w$ and $w^R$ rule then using T to make sure we got $|v| \ge 1$ and Z to create any $|v| > 1$. As I said they are arbitrary non-terminals , you can use this kind of rules as long as they abide by the rules of your language. – Yiğit Aras Tunalı Dec 1 '19 at 12:41
• v has to be greater than 1, because of $v \in \{a,b\}^+$. I think I made a mistake, lemme fix it, because I forgot $w \in \{a,b\}^+$ as well – Yiğit Aras Tunalı Dec 1 '19 at 13:00
• It should be correct now, by $w^R$ I meant if w=ab then $w^R$= ba. – Yiğit Aras Tunalı Dec 1 '19 at 13:44