1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @JohanC yes, it will work $\endgroup$ – nir shahar May 29 at 15:06
0
$\begingroup$

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*}$

$\endgroup$

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.