<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:arial, helvetica, sans-serif;font-size:12pt"><DIV></DIV>
<DIV>> ... then you only have the gui/applet part missing</DIV>
<DIV> </DIV>
<DIV>Thanks a lot for your very informative contribution Yannick. </DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>Stefano<BR> </DIV>Stefano Federici<BR>-------------------------------------------------<BR>Università degli Studi di Cagliari<BR>Facoltà di Scienze della Formazione<BR>Dipartimento di Scienze Pedagogiche e Filosofiche<BR>Via Is Mirrionis 1, 09123 Cagliari, Italia<BR>-------------------------------------------------<BR>Tel: +39 349 818 1955 Fax: +39 070 937 1870
<DIV style="FONT-SIZE: 12pt; FONT-FAMILY: arial, helvetica, sans-serif"><BR><BR>
<DIV style="FONT-SIZE: 12pt; FONT-FAMILY: times new roman, new york, times, serif">----- Messaggio originale -----<BR>Da: Yannick Versley <versley@sfs.uni-tuebingen.de><BR>A: corpora@uib.no<BR>Cc: torbjorn.lager@gmail.com<BR>Inviato: Venerdì 11 aprile 2008, 9:52:47<BR>Oggetto: Re: [Corpora-List] context-DEPENDENT grammar simulator.<BR><BR>well, DCG is prolog, which is turing-complete.<BR><BR>it'd be of course dead simple to write a context-sensitive rewrite system (in <BR>terms of one of the original formulations) in Prolog... then you only have <BR>the gui/applet part missing:<BR><BR>start_symbol(e).<BR>rewrite_rule([a,b],[d]).<BR>rewrite_rule([d,b],[b,d]).<BR>rewrite_rule([d,c],[e]).<BR>rewrite_rule([d,e],[e,d]).<BR>rewrite_rule([e,e],[e]).<BR><BR>parse([X],[]):-start_symbol(X).<BR>parse(Xs,[(Ys->Zs)|Derivation]):-<BR> append(Prefix,Suffix1,Xs),<BR> rewrite_rule(Ys,Zs),<BR>
append(Ys,Rest,Suffix1),<BR> append(Zs,Rest,Suffix2),<BR> append(Prefix,Suffix2,XsNew),<BR> parse(XsNew,Derivation).<BR><BR>with this, you would get something like<BR>?- parse([a,a,b,b,c,c],Deriv).<BR><BR>Deriv = [ ([a, b]->[d]), ([d, b]->[b, d]), ([a, b]->[d]), ([d, c]->[e]), ([d, <BR>e]->[e, d]), ([d, c]->[e]), ([e|...]->[e])]<BR><BR>Yes<BR>?- parse([a,a,a,b,b,c,c],Deriv).<BR><BR>No<BR><BR>Disclaimer 1: I think, but I'm not 100% sure, that the grammar should <BR>recognize only a^n b^n c^n (unless you throw in additional d's or e's).<BR>Disclaimer 2: This is horribly inefficient and will use exponential time. I <BR>think that's unavoidable in the worst case if you want to have general <BR>context-sensitive languages (since they cover everything that a band-limited <BR>Turing machine can do).<BR><BR>Cheers,<BR>Yannick<BR>> >> I think it should be fairly easy to
write an HPSG grammar for the<BR>> >> a^nb^nc^n language using subcat lists [notice the hedges... meaning I<BR>> >> haven't actually done it].<BR>> ><BR>> > I just did it, but in Definite Clause Grammar (DCG):<BR>> ><BR>> > s --> a(N), b(N), c(N).<BR>> ><BR>> > a(0) --> "".<BR>> > a(s(N)) --> [a], a(N).<BR>> ><BR>> > b(0) --> "".<BR>> > b(s(N)) --> [b], b(N).<BR>> ><BR>> > c(0) --> "".<BR>> > c(s(N)) --> [c], c(N).<BR>><BR>> Prolog used to be my favorite programming language, but I forget... I<BR>> presume that s(N) means "successor of N", i.e. the number that comes<BR>> after N (N >= 0; otherwise a 'cut' would be needed to prevent this from<BR>> going on infinitely, with N becoming negative, and no guarantee that the<BR>> a's, b's and c's would then be equal). If that's the right<BR>>
interpretation, then this is taking advantage of the fact that Prolog<BR>> can do infinite arithmetic. But arithmetic cannot be defined in CFPSG,<BR>> AFAIK (beyond the trivial listing of a finite number of arithmetic<BR>> facts), so I don't think this counts as a counterexample to the claim<BR>> that HPSG cannot do strictly CSPSG (or possibly "mildly context<BR>> sensitive PSG").<BR>><BR>> > So that's a context sensitive _language_. I would hesitate to call the<BR>> > DCG a context sensitive _grammar_ though. As far as I remember, a<BR>> > context sensitive grammar has to have a particular form, with rules<BR>> > allowing more than one symbol on the left hand side.<BR>><BR>> That's how it's usually defined, but the unchanged symbols can be moved<BR>> over to an environment, giving you CSPSG rules that look much like<BR>> phonological rules. It's just a different notation. I
suspect DCGs<BR>> have general cspsg capacity, since they can contain arbitrary Prolog<BR>> clauses.<BR><BR>-- <BR>Yannick Versley<BR>Seminar für Sprachwissenschaft, Abt. Computerlinguistik<BR>Wilhelmstr. 19, 72074 Tübingen<BR>Tel.: (07071) 29 77352<BR><BR>_______________________________________________<BR>Corpora mailing list<BR><A href="mailto:Corpora@uib.no" ymailto="mailto:Corpora@uib.no">Corpora@uib.no</A><BR><A href="http://mailman.uib.no/listinfo/corpora" target=_blank>http://mailman.uib.no/listinfo/corpora</A><BR></DIV><BR></DIV></div></body></html>