0
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ What is a stochastic context free grammar? $\endgroup$
    – Tyson Williams
    Aug 31, 2011 at 14:12
  • $\begingroup$ you would probably call it a probabilistic context free grammar $\endgroup$
    – Nathan Harmston
    Aug 31, 2011 at 14:50
  • 3
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Aug 31, 2011 at 15:27
  • 2
    $\begingroup$ 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? $\endgroup$
    – Marzio De Biasi
    Aug 31, 2011 at 15:33
  • $\begingroup$ Let me add that most likely, the question is trivially solved by recursive and exhaustive rule application, bounding at some length for sentences. $\endgroup$
    – Raphael
    Sep 2, 2011 at 7:55

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How does the generating function give you the words? $\endgroup$
    – Raphael
    Sep 2, 2011 at 7:54
  • $\begingroup$ @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. $\endgroup$
    – Mitch
    Sep 2, 2011 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.