 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
dubbi
Clicca QUI per vedere il messaggio nel forum |
| ste182 |
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.... |
| 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 |
| ste182 |
| grazie mille, sei stato molto chiaro:-D |
| misterx |
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 |
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? |
|
|
|
|
