2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

I think you can solve this using this construct:

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Could you explain what T and Z mean in your rules? Do you mean the word backwards with \begin{equation} w^{R} \text { ?} \end{equation} $\endgroup$ – mathflower Dec 1 '19 at 12:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Yiğit Aras Tunalı Dec 1 '19 at 12:41
  • $\begingroup$ So you mean, v can not be greater than 1, because it can not be ϵ because of the +. Right? $\endgroup$ – mathflower Dec 1 '19 at 12:53
  • $\begingroup$ 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 $\endgroup$ – Yiğit Aras Tunalı Dec 1 '19 at 13:00
  • 1
    $\begingroup$ It should be correct now, by $w^R$ I meant if w=ab then $w^R$= ba. $\endgroup$ – Yiğit Aras Tunalı Dec 1 '19 at 13:44

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.