<p>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.</p>

<p>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.</p>

<ul>
<li><p>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. </p></li>
<li><p>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).</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2011-09-02T07:54:58.650Z
How does the generating function give you the words?
Raphael
CC BY-SA 3.0
2011-09-02T14:14:42.933Z
@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
CC BY-SA 3.0
2011-08-31T20:51:51.617Z
2011-08-31T20:51:51.617Z
Mitch
<p>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? </p>

<p>Many thanks in advance </p>

CC BY-SA 3.0
2011-09-02T07:55:54.373Z
Let me add that most likely, the question is trivially solved by recursive and exhaustive rule application, bounding at some length for sentences.
Raphael
CC BY-SA 3.0
2011-08-31T14:12:46.460Z
What is a stochastic context free grammar?
Tyson Williams
CC BY-SA 3.0
2011-08-31T14:50:00.853Z
you would probably call it a probabilistic context free grammar
Nathan Harmston
CC BY-SA 3.0
2011-08-31T15:27:48.227Z
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
CC BY-SA 3.0
2011-08-31T15:33:28.163Z
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
<fl.formal-languages><grammars><software>
Generating a language from a given grammar
Nathan Harmston
# Generating a language from a given grammar

(Asked by: username_0 on 2011-08-31)

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

**Tags:** fl.formal-languages, grammars, software

> **Comments:**
> **username_2**: What is a stochastic context free grammar?  
> **username_0**: you would probably call it a probabilistic context free grammar  
> **username_1**: 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?  
> **username_3**: 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?  
> **username_1**: Let me add that most likely, the question is trivially solved by recursive and exhaustive rule application, bounding at some length for sentences.  

---

## 1 answers

### Answer by username_4 on 2011-08-31. Score: 0 | Accepted 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.

> **Comments:**
> **username_1**: How does the generating function give you the words?  
> **username_4**: @username_1: 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.  

---

