Problem Detail: 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 xAmid yBmid zCmid xmid ymid 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).
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11810
Related
