ste182

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:

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

DarioC

User info:

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

Post actions:

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.

code:

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

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

ste182

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:

grazie mille, sei stato molto chiaro

__________________
Live Fast, Die Fun

misterx

User info:

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

Post actions:

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"

ste182

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:

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