Pages: [1]   Go Down
Print
Author Topic: Esercizio 5.3 - Ausiello  (Read 206 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 28



« on: 26-10-2018, 11:05:27 »

Salve, sto provando a risolvere l'esercizio 5.3 dell'ausiello, il quale richiede di risolvere il seguente problema:

Definire una macchina di Turing deterministica con alfabeto di input
{0, 1} che accetta tutte le stringhe di lunghezza dispari e rifiuta tutte le altre.


La mia soluzione:

Sia M( {0,1} , b(blank), {q0,q1,qf} , q0, {qf}, δ) una macchina di Turing,
con funzione di transizione δ:
_________________________
|δ  |      0     |      1     |     b    |
|----------------------------------|
|q0|{q1,0,d}|{q1,1,d}|     -    |  
|----------------------------------|
|q1|{q0,0,d}|{q0,1,d}|{qf,b,i}|
|----------------------------------|
|qf |      -     |      -      |     -    |
-----------------------------------

E' una soluzione che risolve il problema fornito dall'esercizio?
« Last Edit: 26-10-2018, 12:53:36 by Sain » Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.030



WWW
« Reply #1 on: 26-10-2018, 14:04:41 »

Facciamo controllare a qualche tuo collega.
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.472


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #2 on: 16-11-2018, 23:39:46 »

Scusate, che convenzione accettate per affermare che una certa stringa è accettata?
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 28



« Reply #3 on: 17-11-2018, 17:21:36 »

Sia x una stringa. Essa è accettata da una Macchina di Turing M se e solo se data una computazione
      c1, c2, ..., ck   tale che:

1) c1={q0x} (ovvero la configurazione iniziale di M con input x) ;
2) ci deriva ci+1  per ogni i=1, ..., k-1 ;
3) ck è la configurazione di accettazione.

Quindi se la computazione termina in uno stato finale, la stringa è accettata.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 3.030



WWW
« Reply #4 on: 17-11-2018, 18:33:48 »

Quote
3) ck è la configurazione di accettazione.

Per rispondere alla domanda dovresti appunto dire
che cosa si intende con "configurazione di accettazione".
Logged
Sain
Matricola
*
Offline Offline

Gender: Male
Posts: 28



« Reply #5 on: 19-11-2018, 16:37:36 »

Una configurazione di accettazione è una configurazione c=xqy, tale che x∈ΓΓ'* ∪ {ε}, y∈Γ'*Γ ∪ {blank}, q è uno stato finale, in cui:
Γ è l'alfabeto in input;
Γ' = Γ ∪ {blank}.
« Last Edit: 19-11-2018, 16:47:56 by Sain » Logged
Pages: [1]   Go Up
Print
Jump to: