# 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?

• 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

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