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?

  • $\begingroup$ guys, some valid solution? I haven't understand how to generate the grammar $\endgroup$ – 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.)

  • $\begingroup$ I am sure Jokama gets an "A" for his homework if he adds $S\to\varepsilon$ to your solution. $\endgroup$ – Hendrik Jan Jun 15 '14 at 14:36
  • $\begingroup$ @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. $\endgroup$ – Gilles 'SO- stop being evil' Jun 15 '14 at 14:39
  • $\begingroup$ @HendrikJan, formally $\epsilon$ productions are forbidden in context free grammars. $\endgroup$ – vonbrand Jun 16 '14 at 2:53
  • $\begingroup$ @vonbrand According to which source? Do you mean context-sensitive? $\endgroup$ – Hendrik Jan Jun 16 '14 at 8:21
  • $\begingroup$ I think it's context-free... and if it is context-free is also context-sensitive $\endgroup$ – 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$


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.