[Corpora-List] context-DEPENDENT grammar simulator.

[stefano federici]

> ... then you only have the gui/applet part missing

Thanks a lot for your very informative contribution Yannick. 

As you says, what I really need is a graphical aid to help my students understand "at first glance" the possibility of translating a TM to a grammar and having, as a result, the same computational power.

Stefano
 
Stefano Federici
-------------------------------------------------
Università degli Studi di Cagliari
Facoltà di Scienze della Formazione
Dipartimento di Scienze Pedagogiche e Filosofiche
Via Is Mirrionis 1, 09123 Cagliari, Italia
-------------------------------------------------
Tel: +39 349 818 1955 Fax: +39 070 937 1870



----- Messaggio originale -----
Da: Yannick Versley <versley at sfs.uni-tuebingen.de>
A: corpora at uib.no
Cc: torbjorn.lager at gmail.com
Inviato: Venerdì 11 aprile 2008, 9:52:47
Oggetto: Re: [Corpora-List] context-DEPENDENT grammar simulator.

well, DCG is prolog, which is turing-complete.

it'd be of course dead simple to write a context-sensitive rewrite system (in 
terms of one of the original formulations) in Prolog... then you only have 
the gui/applet part missing:

start_symbol(e).
rewrite_rule([a,b],[d]).
rewrite_rule([d,b],[b,d]).
rewrite_rule([d,c],[e]).
rewrite_rule([d,e],[e,d]).
rewrite_rule([e,e],[e]).

parse([X],[]):-start_symbol(X).
parse(Xs,[(Ys->Zs)|Derivation]):-
    append(Prefix,Suffix1,Xs),
    rewrite_rule(Ys,Zs),
    append(Ys,Rest,Suffix1),
    append(Zs,Rest,Suffix2),
    append(Prefix,Suffix2,XsNew),
    parse(XsNew,Derivation).

with this, you would get something like
?- parse([a,a,b,b,c,c],Deriv).

Deriv = [ ([a, b]->[d]), ([d, b]->[b, d]), ([a, b]->[d]), ([d, c]->[e]), ([d, 
e]->[e, d]), ([d, c]->[e]), ([e|...]->[e])]

Yes
?- parse([a,a,a,b,b,c,c],Deriv).

No

Disclaimer 1: I think, but I'm not 100% sure, that the grammar should 
recognize only a^n b^n c^n (unless you throw in additional d's or e's).
Disclaimer 2: This is horribly inefficient and will use exponential time. I 
think that's unavoidable in the worst case if you want to have general 
context-sensitive languages (since they cover everything that a band-limited 
Turing machine can do).

Cheers,
Yannick
> >>  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).
>
> Prolog used to be my favorite programming language, but I forget... I
> presume that s(N) means "successor of N", i.e. the number that comes
> after N (N >= 0; otherwise a 'cut' would be needed to prevent this from
> going on infinitely, with N becoming negative, and no guarantee that the
> a's, b's and c's would then be equal).  If that's the right
> interpretation, then this is taking advantage of the fact that Prolog
> can do infinite arithmetic.  But arithmetic cannot be defined in CFPSG,
> AFAIK (beyond the trivial listing of a finite number of arithmetic
> facts), so I don't think this counts as a counterexample to the claim
> that HPSG cannot do strictly CSPSG (or possibly "mildly context
> sensitive PSG").
>
> > 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.
>
> That's how it's usually defined, but the unchanged symbols can be moved
> over to an environment, giving you CSPSG rules that look much like
> phonological rules.  It's just a different notation.  I suspect DCGs
> have general cspsg capacity, since they can contain arbitrary Prolog
> clauses.

-- 
Yannick Versley
Seminar für Sprachwissenschaft, Abt. Computerlinguistik
Wilhelmstr. 19, 72074 Tübingen
Tel.: (07071) 29 77352

_______________________________________________
Corpora mailing list
Corpora at uib.no
http://mailman.uib.no/listinfo/corpora
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.linguistlist.org/pipermail/corpora/attachments/20080411/2e481b4e/attachment.htm>
-------------- next part --------------
_______________________________________________
Corpora mailing list
Corpora at uib.no
http://mailman.uib.no/listinfo/corpora