I have this language:$$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$where $|w|_a$ is the number of occurrences of $a$.How can I find a grammar that generates it?
Grammar for a language with 1/3 of a's
formal languages;context free;formal grammars
The proportion of $a$'s has to be $1/3$. This means that every $a$ encountered in the word creates a debt that must be compensated by two non-$a$'s. This way of looking at the language rather directly leads to a pushdown automaton. With a bit more reasoning, it also leads to a language.If the word starts with $a$, that $a$ must be compensated by two non-$a$'s. These two compensating letters might not come immediately: the word can start with multiple $a$'s. But eventually the $a$ debt has to be reduced back to the starting $a$, and then a non-$a$ takes the debt down. Each $a$ can be said to have two matching non-$a$'s: the ones that take the debt down from the level where that $a$ put it. In other words, an initial $a$ can be followed by any number of elements of $L$ (each element of $L$ leaves the $a$ debt constant), then a compensating non-$a$, then more elements of $L$, then the second compensating non-$a$, and finally more elements of $L$.The same principle applies if the word starts with a non-$a$. The trio of $a$, non-$a$ and non-$a$ can come in any order: the $a$ could be either second or third if it isn't first.$$ \begin{align}  S &\to \\  S &\to a \, S \, B \, S \, B \, S \\  S &\to B \, S \, a \, S \, B \, S \\  S &\to B \, S \, B \, S \, a \, S \\  B &\to b \mid c \\\end{align} $$It's clear by induction on the length of the word that any word generated by this grammar is in $L$. (Write it down.) Conversely, the reasoning above shows that all words in $L$ can be decomposed according to the grammar above, again by induction on the length of the word. (Again, write it down.)