World's most popular travel blog for travel bloggers.

# [Solved]: Grammar for a language with 1/3 of a's

, ,
Problem Detail:

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?

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.)