Context free grammar of $L = \{w \in \{a, b, c\}^* : |w|_{c} = 3k +1 \}$

74 Views Asked by At

So, this is my first homework in conext free grammar, I want the grammar that generates all possible words in L, I have come out with the following rules $$ S \rightarrow aS | bS| cX\\ X \rightarrow aX| bX| cY\\ Y \rightarrow aY|bY|cZ|cS\\ Z \rightarrow aZ|bZ |cK\\ K \rightarrow aK| bK| a| b| \epsilon $$

but it does not generate words of for wc where c is not in w.

1

There are 1 best solutions below

2
On BEST ANSWER

You seem to have the right idea, but as you say, you're missing the case where $c$ is at the end of the word. Moreover, no word generated by your grammar has less than $4$ $c$'s in it, i.e. you're missing the case where $|w|_c = 1$.

I think the problem is that you have too many states. You just need the three states for the number of $c$'s modulo $3$. You start in $S$ can be $0$ mod $3$, $X$ can be $1$ mod $3$, and $Y$ can be $2$ mod $3$. You move between these states by adding another $c$, stay in the states by adding $a$ or $b$, and you can only terminate from state $X$. That is, I suggest:

\begin{align*} S &\to aS \mid bS \mid cX \\ X &\to aX \mid bX \mid cY \mid \varepsilon \\ Y &\to aY \mid bY \mid cS. \end{align*}