|
ste182 |
|
|
ste182 |
.arcimaestro.
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline
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 |
|
|
| |
|
DarioC |
Beh, non puoi sapere a priori se un programma term ... |
08-07-2010 19:27 |
|
|
DarioC |
.amico.
Registered: Mar 2009
Posts: 23 (0.00 al dì)
Location: Amsterdam
Corso: Informatica
Anno: Dottore! (BSc)
Time Online: 5:31:32 [...]
Status: Offline
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 |
|
|
| |
|
ste182 |
grazie mille, sei stato molto chiaro:-D ... |
08-07-2010 23:41 |
|
|
ste182 |
.arcimaestro.
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline
Edit | Report | IP: Logged |
grazie mille, sei stato molto chiaro
__________________
Live Fast, Die Fun
|
08-07-2010 23:41 |
|
|
| |
|
misterx |
[QUOTE][i]Originally posted by DarioC [/i]
... |
09-07-2010 18:21 |
|
|
misterx |
.illuminato.
Registered: Sep 2003
Posts: 154 (0.02 al dì)
Location:
Corso:
Anno:
Time Online: 23:24:56 [...]
Status: Offline
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 |
|
|
| |
|
ste182 |
ciao, avrei un altro dubbio:
... |
14-07-2010 17:34 |
|
|
ste182 |
.arcimaestro.
Registered: Oct 2004
Posts: 258 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 2 Days, 5:06:07: [...]
Status: Offline
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 |
|
|
| |
|
All times are GMT. The time now is 21:39. |
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|