"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