# Context-free Grammar Exercise

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

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

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.
• Could you explain what T and Z mean in your rules? Do you mean the word backwards with $$w^{R} \text { ?}$$ – mathflower Dec 1 '19 at 12:38
• 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