Need help in formal grammar for the $L = \{wcw : w \in \{a,b\}^\ast\}$

Question

I can't create formal grammar for the language like

$wcw$ where $w$ is the word in $\{a,b\}^\ast$ and $c$ is just a letter

Thanks!

Answer 1

Hint (but I did not check all details, so I apologize if I've overseen some problem there):

Would you be able to make a grammar in which this would be a derivation?

$S \Rightarrow^* ABBS \Rightarrow^* A_1B_1B_1S_1A_3B_3B_3 \Rightarrow^* abbcabb$

Of course, $S$, $A$, $B$, $A_1$, $B_1$, $A_2$, $B_2$, $A_3$, $B_3$ are non-terminals, $a$, $b$ are terminals.

EDIT: I've added two more non-terminals. (In the approach I have in mind I will need them to distinguish whether the letter has already "moved" to the right half.)

---

I've tried too google a little, mainly for the reason that I did not want put energy into writing up a solution if it was already given elsewhere.

Searching for "formal language" grammar "wcw" and similar phrases led me to this paper (Wayback Machine). Some grammar for this language is given there. But it is not the type of grammar you're looking for - it's a Boolean grammar. But since the author mentions that this is one of the standard examples of non-context-free constructs, this suggest that this should probably not be too difficult and this example could occur in some standard textbooks.

The fact that it is not context-free should be provable using pumping lemma; a complete proof of this fact is given in Johan Jeuring, Doaitse Swierstra: Grammars and Parsing (Wayback Machine), which is basically a collection of solved exercises (with solutions).

Answer 2

A solution: $$\begin{align*} \Sigma & \to \mathtt{c} & \tag{1} \\ \Sigma & \to i \mathtt{c} i & \mathrm{for} \: i \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{2} \\ \Sigma & \to i C_{j} A_{i} S_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{3} \\ C_{i} A_{j} & \to D_{i} A_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{4} \\ D_{i} A_{j} & \to D_{i} B_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{5} \\ B_{i} A_{j} & \to B_{i} B_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{6} \\ B_{i} S_{j} & \to B_{i} X_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{7} \\ B_{i} S_{j} & \to B_{i} Y_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{8} \\ B_{i} X_{j} & \to T_{i} X_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{9} \\ B_{i} Y_{j} & \to F_{i} Y_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{10} \\ B_{i} T_{j} & \to T_{i} T_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{11} \\ B_{i} F_{j} & \to F_{i} F_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{12} \\ D_{i} T_{j} & \to \mathtt{a} C_{i} T_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{13} \\ D_{i} F_{j} & \to \mathtt{b} C_{i} F_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{14} \\ C_{i} T_{j} & \to C_{i} Z_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{15} \\ C_{i} F_{j} & \to C_{i} Z_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{16} \\ Z_{i} T_{j} & \to Z_{i} Z_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{17} \\ Z_{i} F_{j} & \to Z_{i} Z_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{18} \\ Z_{i} X_{j} & \to Z_{i} A_{\mathtt{a}} S_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{19} \\ Z_{i} Y_{j} & \to Z_{i} A_{\mathtt{b}} S_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{20} \\ Z_{i} A_{j} & \to A_{i} A_{j} & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{21} \\ S_{i} & \to i & \mathrm{for} \: i \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{22} \\ A_{i} j & \to i j & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{23} \\ C_{i} j & \to i \mathtt{c} j & \mathrm{for} \: i , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} \tag{24} \end{align*}$$

The idea of this context-sensitive grammar is similar to that of 4-stroke engine:

1. the sentential form $$i_{1} i_{2} \cdots i_{n} C_{j} A_{i_{1}} A_{i_{2}} \cdots A_{i_{n}} S_{j}$$ becomes either $$ i_{1} i_{2} \cdots i_{n} D_{j} B_{i_{1}} B_{i_{2}} \cdots B_{i_{n}} S_{j} \tag{go to 2} $$ by $\left( 4 \right)$, $\left( 5 \right)$ and $\left( 6 \right)$ or $$ i_{1} i_{2} \cdots i_{n} j \mathtt{c} i_{1} i_{2} \cdots i_{n} j \tag{end} $$ by $\left( 22 \right)$, $\left( 23 \right)$ and $\left( 24 \right)$;
2. the sentential form $$i_{1} i_{2} \cdots i_{n} D_{j} B_{i_{1}} B_{i_{2}} \cdots B_{i_{n}} S_{j}$$ becomes either $$ i_{1} i_{2} \cdots i_{n} D_{j} T_{i_{1}} T_{i_{2}} \cdots T_{i_{n}} X_{j} \tag{go to 3} $$ by $\left( 7 \right)$, $\left( 9 \right)$ and $\left( 11 \right)$ or $$ i_{1} i_{2} \cdots i_{n} D_{j} F_{i_{1}} F_{i_{2}} \cdots F_{i_{n}} Y_{j} \tag{go to 4} $$ by $\left( 8 \right)$, $\left( 10 \right)$ and $\left( 12 \right)$;
3. the sentential form $$i_{1} i_{2} \cdots i_{n} D_{j} T_{i_{1}} T_{i_{2}} \cdots T_{i_{n}} X_{j}$$ becomes $$ i_{1} i_{2} \cdots i_{n} \mathtt{a} C_{j} Z_{i_{1}} Z_{i_{2}} \cdots Z_{i_{n}} X_{j} \tag{go to 5} $$ by $\left( 13 \right)$, $\left( 15 \right)$ and $\left( 17 \right)$;
4. the sentential form $$i_{1} i_{2} \cdots i_{n} D_{j} F_{i_{1}} F_{i_{2}} \cdots F_{i_{n}} Y_{j}$$ becomes $$ i_{1} i_{2} \cdots i_{n} \mathtt{b} C_{j} Z_{i_{1}} Z_{i_{2}} \cdots Z_{i_{n}} Y_{j} \tag{go to 6} $$ by $\left( 14 \right)$, $\left( 16 \right)$ and $\left( 18 \right)$;
5. the sentential form $$i_{1} i_{2} \cdots i_{n} \mathtt{a} C_{j} Z_{i_{1}} Z_{i_{2}} \cdots Z_{i_{n}} X_{j}$$ becomes $$ i_{1} i_{2} \cdots i_{n} \mathtt{a} C_{j} A_{i_{1}} A_{i_{2}} \cdots A_{i_{n}} A_{\mathtt{a}} S_{j} \tag{go to 1} $$ by $\left( 19 \right)$ and $\left( 21 \right)$;
6. the sentential form $$i_{1} i_{2} \cdots i_{n} \mathtt{b} C_{j} Z_{i_{1}} Z_{i_{2}} \cdots Z_{i_{n}} Y_{j}$$ becomes $$ i_{1} i_{2} \cdots i_{n} \mathtt{b} C_{j} A_{i_{1}} A_{i_{2}} \cdots A_{i_{n}} A_{\mathtt{b}} S_{j} \tag{go to 1} $$ by $\left( 20 \right)$ and $\left( 21 \right)$;

where $ n \geq 1 $, $ i_{1} , i_{2} , \cdots i_{n} , j \in \left\{ \mathtt{a} , \mathtt{b} \right\} $.

An example: $$\begin{align*} \Sigma & \implies \mathtt{a} C_{\mathtt{b}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 3 \right) \\ & \implies \mathtt{a} D_{\mathtt{b}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 4 \right) \\ & \implies \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 5 \right) \\ & \implies \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} X_{\mathtt{b}} & \mathrm{by} \: \left( 7 \right) \\ & \implies \mathtt{a} D_{\mathtt{b}} T_{\mathtt{a}} X_{\mathtt{b}} & \mathrm{by} \: \left( 9 \right) \\ & \implies \mathtt{a} \mathtt{a} C_{\mathtt{b}} T_{\mathtt{a}} X_{\mathtt{b}} & \mathrm{by} \: \left( 13 \right) \\ & \implies \mathtt{a} \mathtt{a} C_{\mathtt{b}} Z_{\mathtt{a}} X_{\mathtt{b}} & \mathrm{by} \: \left( 15 \right) \\ & \implies \mathtt{a} \mathtt{a} C_{\mathtt{b}} Z_{\mathtt{a}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 19 \right) \\ & \implies \mathtt{a} \mathtt{a} C_{\mathtt{b}} A_{\mathtt{a}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 21 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} A_{\mathtt{a}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 4 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} A_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 5 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} B_{\mathtt{a}} S_{\mathtt{b}} & \mathrm{by} \: \left( 6 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} B_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 8 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} B_{\mathtt{a}} F_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 10 \right) \\ & \implies \mathtt{a} \mathtt{a} D_{\mathtt{b}} F_{\mathtt{a}} F_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 12 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} F_{\mathtt{a}} F_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 14 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} Z_{\mathtt{a}} F_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 16 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} Z_{\mathtt{a}} Z_{\mathtt{a}} Y_{\mathtt{b}} & \mathrm{by} \: \left( 18 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} Z_{\mathtt{a}} Z_{\mathtt{a}} A_{\mathtt{b}} S_{\mathtt{b}} & \mathrm{by} \: \left( 20 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} Z_{\mathtt{a}} A_{\mathtt{a}} A_{\mathtt{b}} S_{\mathtt{b}} & \mathrm{by} \: \left( 21 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} A_{\mathtt{a}} A_{\mathtt{a}} A_{\mathtt{b}} S_{\mathtt{b}} & \mathrm{by} \: \left( 21 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} A_{\mathtt{a}} A_{\mathtt{a}} A_{\mathtt{b}} \mathtt{b} & \mathrm{by} \: \left( 22 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} A_{\mathtt{a}} A_{\mathtt{a}} \mathtt{b} \mathtt{b} & \mathrm{by} \: \left( 23 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} A_{\mathtt{a}} \mathtt{a} \mathtt{b} \mathtt{b} & \mathrm{by} \: \left( 23 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} C_{\mathtt{b}} \mathtt{a} \mathtt{a} \mathtt{b} \mathtt{b} & \mathrm{by} \: \left( 23 \right) \\ & \implies \mathtt{a} \mathtt{a} \mathtt{b} \mathtt{b} \mathtt{c} \mathtt{a} \mathtt{a} \mathtt{b} \mathtt{b} & \mathrm{by} \: \left( 24 \right) \end{align*}$$