# Is there a grammar for this language? $w^{m-1}aca^m$?

I have to form a free context grammar for this language $$w^{m-1}aca^m$$ where $$w \in \{a,b\}$$, so what I have been able to do is this:

$$X \rightarrow SacA$$
$$S \rightarrow aS|bS$$
$$A \rightarrow aA$$

But I don't know how to do it or if possible, condition the exponents as long as $$S$$ is repeated $$m-1$$ times, and $$A$$, $$m$$ times.

You attack it from the exact wrong side.

First, the language is the same as $$\{w^m aca a^m|w\in\{a,b\},m\in\mathbb{N}\}$$. For this, you apply a rule that adds $$w$$ on the left and $$a$$ on the right repeatedly, and then inserts $$aca$$ in the middle and is done. By using one rule that adds both on the left and the right side, you make the number of w's and a's the same.

$$S \rightarrow WSa$$
$$S \rightarrow aca$$
$$W \rightarrow a|b$$

That’s it.

• @JohanC yes, it will work – nir shahar May 29 at 15:06

If the question is really about $$w \in \{ a, b \}$$ (i.e., $$w$$ is an $$a$$ or a $$b$$), a grammar would be:

\begin{align*} S &\to a A a \mid b B a \\ A &\to a A a \mid a c a \\ B &\to b B a \mid a c a \end{align*}