1

create a context free grammar that creates this language: $\{w_1bw_2bw_3 : w_1,w_2,w_3\in \{a,c\}^* \space\text{and}\space |w_2|+|w_3|<2|w_1|\}$

Usually when I solve context free grammar questions, I try to find where the $2$ parts that I need to "count" or "save" or "compare", for example if I want to make a context free grammar that creates palindromes, I know that the trick is creating two similar words, for example $S\to aSa|bSb|a|b|\epsilon$.

This question is confusing me as the two parts aren't clear for me, I'm not getting how I'm supposed to keep track of three parts together with $b's$ in between them.

I would appreciate any help, thanks in advance.

Pwaol
  • 2,113

1 Answers1

1

Decompose the word structure as $(w_1)b(w_2bw_3)$ and produce words starting from the $b$. The length condition can be conveniently rewritten as $|w_2bw_3|\le2|w_1|$ – for every symbol produced for $w_1$ at most two can be produced for $w_2bw_3$. The condition that $w_2bw_3$ has exactly one $b$ is implemented by the start symbol $S$ changing into $T$ once it produces the second $b$. $$S\to XSY|XTP\\ T\to XTY|b\\ X\to a|c\\ Y\to XX|X|\varepsilon\\ P\to bX|Xb|b$$ Note that zero $X$'s cannot be produced by this CFG left of the first $b$, but this is OK since there are no words in the language with $|w_1|=0$.

Parcly Taxel
  • 103,344