Dsy Network www | forum | my | didattica | howto | wiki | el goog | stats | blog | dona | rappresentanti
Homepage
 Register   Calendar   Members  Faq   Search  Logout 
.dsy:it. : Powered by vBulletin version 2.3.1 .dsy:it. > Didattica > Corsi G - M > Linguaggi formali e automi > dubbi
  Last Thread   Next Thread
Author
Thread    Post New Thread    Post A Reply
ste182
.arcimaestro.

User info:
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged
dubbi

ciao ragazzi, ho un pò di dubbi:
definisco un linguaggio L = {x | x appartiene {0,1}*, U(x$x) termina }
quindi un linguaggio formato da parole x formate da tutte le possibili combinazioni di 0,1 compresa la parola vuota, tale che l'interprete su input x,x termina.
e qui mi chiedo: se x è un programma, gli viene dato come input se stesso è ovvio che termina, quindi x appartiene a L. Quale sarebbe il caso in cui non termina?? non riesco a capire...dato che l'input dell'interprete è sempre fatto eseguire su se stesso...
cioè mettiamo che gli do in input y (sempre in {0,1}* ), sarà come fare U(y$y) quindi ancora termina....

__________________
Live Fast, Die Fun

17-06-2010 19:03
Click Here to See the Profile for ste182 Click here to Send ste182 a Private Message Find more posts by ste182 Add ste182 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
DarioC
.amico.

User info:
Registered: Mar 2009
Posts: 23 (0.01 al dì)
Location: Amsterdam
Corso: Informatica
Anno: Dottore! (BSc)
Time Online: 5:31:32 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Beh, non puoi sapere a priori se un programma termina o no, quando riceve come input se stesso, ad esempio considera questo programma, che termina solo se il primo carattere della stringa che riceve è una 'A':

code:
Procedure PROG(char x[]) begin while (x[0] != 'A') write("Ciao"); end.


Se gli dai come input se stesso la prima lettera della stringa è una 'P' (la 'P' di 'Procedure PROG(ecc...')

Questo è un programma che, se riceve in input il suo stesso codice, genera una computazione infinita (e per la precisione stampa infiniti "Ciao").

Poi non è detto che la terminazione del programma debba sempre dipendere dal parametro:

code:
Procedure PROG2(x) begin while ( TRUE ) printf("Ciao"); end.


Questo programma non termina mai, neppure nel caso in cui riceva come input il suo stesso codice...

Ciao!
Dario

Last edited by DarioC on 08-07-2010 at 19:34

08-07-2010 19:27
Click Here to See the Profile for DarioC Click here to Send DarioC a Private Message Visit DarioC's homepage! Find more posts by DarioC Add DarioC to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
ste182
.arcimaestro.

User info:
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

grazie mille, sei stato molto chiaro:-D

__________________
Live Fast, Die Fun

08-07-2010 23:41
Click Here to See the Profile for ste182 Click here to Send ste182 a Private Message Find more posts by ste182 Add ste182 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
misterx
.illuminato.

User info:
Registered: Sep 2003
Posts: 154 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 23:24:56 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Originally posted by DarioC
Beh, non puoi sapere a priori se un programma termina o no, quando riceve come input se stesso, ad esempio considera questo programma, che termina solo se il primo carattere della stringa che riceve è una 'A':

code:
Procedure PROG(char x[]) begin while (x[0] != 'A') write("Ciao"); end.


Se gli dai come input se stesso la prima lettera della stringa è una 'P' (la 'P' di 'Procedure PROG(ecc...')

Questo è un programma che, se riceve in input il suo stesso codice, genera una computazione infinita (e per la precisione stampa infiniti "Ciao").

Poi non è detto che la terminazione del programma debba sempre dipendere dal parametro:

code:
Procedure PROG2(x) begin while ( TRUE ) printf("Ciao"); end.


Questo programma non termina mai, neppure nel caso in cui riceva come input il suo stesso codice...

Ciao!
Dario



non immaginavo che si intendesse semplicemente quello come "input se stesso" :)

09-07-2010 18:21
Click Here to See the Profile for misterx Click here to Send misterx a Private Message Find more posts by misterx Add misterx to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
ste182
.arcimaestro.

User info:
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

ciao, avrei un altro dubbio:

data una grammatica G= <{a}, {S,A,B}, {S->aA, A->aB, B->ɛ}, S> che ovviamente genera la parola "aa"del linguaggio L.
modifico la grammatica in modo da avere il linguaggio L* (chiusura di kleene):
G1= <{a}, {S,A,B}, {S->aA, A->aB, B->ɛ, B->S}, S>
ora per passare all'automa X che riconosce il linguaggio L*(generato da G1) procedo così:
- gli stati di X sono i metasimboli della grammatica, quindi q0=S, q1=A, q2=B
- l'alfabeto è lo stesso
- la funzione di transizione f:QxQ->{a}
- stati finali = q2
- stato iniziale = q0

ora se disegnamo l'automa otteniamo questo:

però questo riconosce solo la parola "aa", quindi la regola B->S(q2->q0) come la traduco?cioè cosa devo mettere come input sull'arco che parte da q2 e torna su q0 in modo da poter ricominciare da capo e riconoscere quindi L*(che in questo caso mi sembra L+ dato che la parola vuota non può essere generata)?? per caso l'input sull'arco da q2 a q0 è la parola vuota? in quel caso si genera un automa non deterministico perchè q2->ɛq2 e q2->ɛq0, giusto?

__________________
Live Fast, Die Fun

Last edited by ste182 on 14-07-2010 at 17:47

14-07-2010 17:34
Click Here to See the Profile for ste182 Click here to Send ste182 a Private Message Find more posts by ste182 Add ste182 to your buddy list Printer Friendly version Email this Article to a friend Reply w/Quote
All times are GMT. The time now is 09:40.    Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread | Add to Bookmarks

Forum Jump:
Rate This Thread:

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
 

Powered by: vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento | Licenze | Thanks | Syndacate
Pagina generata in 0.044 seconds (59.11% PHP - 40.89% MySQL) con 30 query.