[Corpora-List] context-DEPENDENT grammar simulator.

[Rob Malouf]

> Rob Malouf wrote:
>> NLTK also supports context sensitive grammars,
>> in the form of feature-based grammars...
>
> AFAIK, the use of features, even when it enforces agreement, does  
> not make
> a grammar context-sensitive; and I don't believe the feature-based
> grammars in NLTK have context-sensitive power.  The theory of HPSG  
> (and
> before that, GPSG) is based on the assumption that feature grammars  
> are
> still context-free.

This is maybe drifting too far off topic... but I'm pretty sure  
that's not the case.  GPSG is context-free -- that's the whole point  
of it -- but only because the features all have a finite number of  
possible values.  That lets you "compile" the feature bundles into  
atomic categories and convert the feature-based rules into context- 
free rules.  In HPSG and other similar unification-based formalisms,  
though, the value of a feature can be another whole feature bundle,  
so there's no way to compile an HPSG into a CFG with a finite number  
of non-terminals.  That what gets you context-sensitive power: e.g.,  
I think it should be fairly easy to write an HPSG grammar for the  
a^nb^nc^n language using subcat lists [notice the hedges... meaning I  
haven't actually done it].

> There are very few examples in natural language that seem to require
> anything more than context-free grammars, and there's a substantial
> literature on those few examples of "mild context sensitivity."
> Tree-Adjoining Grammars (TAGs) are claimed to have the  
> appropriately mild
> context sensitive power.

Indeed.  There's been quite a bit of work on (successfully)  
translating big grammars between HPSG and TAG formalisms, which makes  
me think that the extra formal power that HPSG has doesn't really get  
much use in practical linguistic applications.

---
Rob Malouf <rmalouf at mail.sdsu.edu>
Department of Linguistics and Asian/Middle Eastern Languages
San Diego State University


_______________________________________________
Corpora mailing list
Corpora at uib.no
http://mailman.uib.no/listinfo/corpora