[Corpora-List] context-DEPENDENT grammar simulator.

[Torbjörn Lager]

On Thu, Apr 10, 2008 at 6:27 PM, Rob Malouf <rmalouf at mail.sdsu.edu> wrote:
> > Rob Malouf wrote:
...
>  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].

I just did it, but in Definite Clause Grammar (DCG):

s --> a(N), b(N), c(N).

a(0) --> "".
a(s(N)) --> [a], a(N).

b(0) --> "".
b(s(N)) --> [b], b(N).

c(0) --> "".
c(s(N)) --> [c], c(N).


?- s(S,[]).
S = [] ;
S = [a, b, c] ;
S = [a, a, b, b, c, c] ;
S = [a, a, a, b, b, b, c, c, c] ;
....

So that's a context sensitive _language_. I would hesitate to call the
DCG a context sensitive _grammar_ though. As far as I remember,  a
context sensitive grammar has to have a particular form, with rules
allowing more than one symbol on the left hand side.

Regards,
Torbjörn

On Thu, Apr 10, 2008 at 6:27 PM, Rob Malouf <rmalouf at mail.sdsu.edu> wrote:
> > 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
>

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