# Grammar for a language with 1/3 of a's

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?

• guys, some valid solution? I haven't understand how to generate the grammar – Jokama Jun 15 '14 at 14:04

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

• I am sure Jokama gets an "A" for his homework if he adds $S\to\varepsilon$ to your solution. – Hendrik Jan Jun 15 '14 at 14:36
• @HendrikJan I could pretend that was deliberate, but I won't. Never trust an answer without a formal proof! Thanks. By the way, feel free to edit in such cases. – Gilles 'SO- stop being evil' Jun 15 '14 at 14:39
• @HendrikJan, formally $\epsilon$ productions are forbidden in context free grammars. – vonbrand Jun 16 '14 at 2:53
• @vonbrand According to which source? Do you mean context-sensitive? – Hendrik Jan Jun 16 '14 at 8:21
• I think it's context-free... and if it is context-free is also context-sensitive – Jokama Jun 16 '14 at 10:39

Suppose that you are given a word $w$ in the language. You can extend it by taking any word in the language and inserting it anywhere in $w$. The following rule generates the smallest non-empty words in the language:

$S \to \text{ a T T } | \text{ T T a } | \text{ T a T }$

$T \to b\text{ }|\text{ }c$

The first paragraph suggests that the grammar is given by:

$S \to \text{ S a S T S T S } | \text{ S T S T S a S } | \text{ S T S a S T S } | \text{ }\epsilon$

$T \to b\text{ }|\text{ }c$