"Arbitrary" context free grammars?

Posted by danwroy on Stack Overflow See other posts from Stack Overflow or by danwroy
Published on 2010-06-17T00:05:54Z Indexed on 2010/06/17 0:12 UTC
Read the original article Hit count: 337

Long time admirer first time inquirer :)

I'm working on a program which derives a deterministic finite-state automata from a context-free grammar, and the paper I have been assigned which explains how to do this keeps referring to "arbitrary probabilistic context-free grammars" but never defines the meaning of "arbitrary" in relation to PCFGs. I assume they mean "any old PCFG" but then why not just say "any PCFG"?

The term also turns up in several Wikipedia entries. At the top of the CFG page there is a reference to arbitrariness in relation to CFGs on ("clauses can be nested inside clauses arbitrarily deeply"), but doesn't make clear why someone would refer to a PCFG or subset of PCFGs as arbitrary.

In case anyone is curious, the paper is Parsing and Hypergraphs by Klein and Manning (2001); I've also been reading two other papers by them related to this one (An Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars and Empirical Bounds, Theoretical Models, and the Penn Treebank) which use the term extensively but never explain it either.

Thanks for your help!

© Stack Overflow or respective owner

Related posts about terminology

Related posts about context-free-grammar