.dsy:it. - dubbi

.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- dubbi (http://www.dsy.it/forum/showthread.php?threadid=40612)

Posted by ste182 on 17-06-2010 19:03:

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

Posted by DarioC on 08-07-2010 19:27:

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

Posted by ste182 on 08-07-2010 23:41:

grazie mille, sei stato molto chiaro :-D

__________________
Live Fast, Die Fun

Posted by misterx on 09-07-2010 18:21:

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"

Posted by ste182 on 14-07-2010 17:34:

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

All times are GMT. The time now is 06:55.

Show all 5 posts from this thread on one page