# Generating a language from a given grammar

So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there any software out there that does this? Or a library?

Many thanks in advance

• What is a stochastic context free grammar? – Tyson Williams Aug 31 '11 at 14:12
• you would probably call it a probabilistic context free grammar – Nathan Harmston Aug 31 '11 at 14:50
• For the set of generated words it does not matter wether you have a stochastic or a normal grammer. Nathan, as there are typically infinitely many words, what exactly do you want? – Raphael Aug 31 '11 at 15:27
• For "all words" do you mean "all words up to a finite length $n$"? Do you need to calculate the associated word-probabilities, too? Do you need a generic software or are you interested in a particular area such as NLP or biomedics? – Marzio De Biasi Aug 31 '11 at 15:33
• Let me add that most likely, the question is trivially solved by recursive and exhaustive rule application, bounding at some length for sentences. – Raphael Sep 2 '11 at 7:55

## 1 Answer

Since you want to generate -all- words of a given length, it really doesn't matter if it's stochastic/probabilistic or deterministic, you just want to see if a word is possible (the following method should be modifiable to also compute the probability of any given word.

Two methods, one theoretical and cool and programmable in a couple lines of inscrutable Mathematica, or a practical efficient algorithm which I'd rather not both to code in ML/Haskell.

• you can interpret a (context free) grammar as defining a set of polynomials equations (the way the theory works, you just can't do this for context-sensitve or worse grammars). Use Groebner bases to simplify the system, and solve for the generating function, from which you can then extract the number of -derivations- (we don't now if it's unambiguous) of words of a given size. Yes, that is a short sentence to describe the work you'd have to do, and that's not even from scratch. (For a regular grammar, Groebner bases is kind of a jack hammer when all you need is the small jeweler's hammer of the Kleene algorithm to generate the regular expression for the language from the right linear grammar converted to NFA. And then the generating function can (almost!) be read straight off from the regexp.

• a way to implement the above, bypassing all the intensive algebraic manipulation, don't bother with all that fix-point computation (that's really what the algebraic manipulation is doing for you). Instead, create a vector of length $n$ for each variable, set them all to 0's. Then operate on each rule thinking of union as vector addition and concatenation as vector convolution (if A <- B C, then $a_k = \sum a_j b_{k-j}$, and the base case is a terminal which is $\langle 0,1,0,0,0,0... \rangle$. (this method might work for CSGs but I think it takes longer to converge).

I'm sure there's an easier way to do it in a straightforward manner, but you know how it is, sometimes the complicated big guns that take a steep learning curve to manage are some how more familiar and easier to think about than an obvious simple solution.

• How does the generating function give you the words? – Raphael Sep 2 '11 at 7:54
• @Raphael: good question (because I didn't realize that there might be problems). The generating function for a regular expression will only involve addition, multiplication, and 1/(1-f(x)) (the gf analog of Kleene closure). There are straightforward techniques for turning those into actually generating (a la Wilf) the actual strings (see work by Flajolet). As to the more general CFGs, off the top of my head I can't remember how to do string generation more directly from the square roots in a solution to a polynomial equation. – Mitch Sep 2 '11 at 14:14