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
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 &lt;- 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.