2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ if you find my english is bad (or worst ever) edit please! $\endgroup$ – Alejandro Sazo May 5 '13 at 18:40
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

enter image description here

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.

enter image description here

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

$\endgroup$

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.