# 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? Aug 31, 2011 at 14:12
• you would probably call it a probabilistic context free grammar Aug 31, 2011 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? Aug 31, 2011 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? Aug 31, 2011 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. Sep 2, 2011 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).