Easiest way to write a grammar?

Question

When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:

Let $L$ a language which alphabet is $\{x,y,z\}$ and accepts strings $w$ where there aren't consecutive $x$'s nor consecutive $y$'s nor consecutive $z$'s.

My first aproaching was to stablish that $x$, $y$ and $z$ each one are in $L$, that is:

$$S \rightarrow x \mid y \mid z$$

If the string has an $x$, there can be a consecutive $y$ or $z$, similarly for the other symbols. I assume that there are productions $A$, $B$ and $C$ that make the work, so the start production is:

$$S \rightarrow xA\mid yB\mid zC\mid x\mid y\mid z$$

Therefore $S$ can be splitted to define $A$, $B$ and $C$:

$\begin{eqnarray*}S &\rightarrow& A \mid B \mid C \\A &\rightarrow& yB \mid zC \mid y \mid z \\ B &\rightarrow& xA \mid zC \mid x \mid z\\ C &\rightarrow& xA \mid yB \mid x \mid y \end{eqnarray*}$

But as you all can see this is just my version, I started with base strings accepted by $L$ and then I followed my own thought of how to build the grammar. Is there a easy way to do this? or some advice for similar languages? (like those which have different number of symbols).

Answer 1

Of course "instinct"always helps, but writing a grammar is more or less writing a program, but with limited resources.

Your example matches a regular language. Those languages can be defined using right-linear grammars but I prefer finite state automata. Programming linear grammars (and finite state automata) requires thinking in states. What is the characteristic information about the string I have seen so far.

In your example the "state" consists of the last letter read. OK, since your task is to avoid reading a letter twice. In other examples you might want to do some counting ("if the string contains exactly four $a$'s it ends in $b$") or modulo counting ("the number of $a$'s is even"). Perhaps you want to do a kind of pattern recognition ("words that do not contain $00110$") and you keep track of the part of the pattern you have just seen.

Sometimes the requirements consist of a Boolean combination of properties. Then you keep track of both of them in the state and react on what you know.

You see: just like programming.

If the grammar is more complicated, like context-free you probably want to think in terms of trees. That is the structure they use to derive strings.

Answer 2

The language you are describing is regular. Thinking in terms of states, as Hendrik Jan points, is helpful. If you are scanning a string for acceptance or rejection, then after reading one character (say $x$) you want the next one to be a member of ($\Sigma - \{x\}$).

An automaton for this language can have a state per alphabet symbol. So you could start by sketching the following:

A valid string can start by any alphabet symbol, so we have to add a start state with epsilon-moves to the remaining states. A valid string can end in any alphabet symbol as well, so every state is accepting. We get the following non-deterministic FSA.

You can get a right-reglar grammar by determinizing the above automaton.