Masini Turing problema
3
Tema MT. gr. 234 Ion Ureche. (Problema 22) Enun : Se dă un cuvânt nevid format cu literele {a,b,c} amestecate. Să se accepte intrarea dacă este de forma w w^R w (notam cu w^R cuvântul w oglindit, R = inversul său / reverse). Exemplu: Fie w = abcaa, atunci cuvântul de pe bandă abcaaaacbaabcaa Va fi acceptat. Ideea de rezolvare: Vom afla unde se termina cuvântul de bază (w) după care de la capătul lui vom verifica egalitatea cu w^R, din dreapta sa. Apoi vom verifica egalitatea lui w, cu w` (cel de la finalul benzii). Pa ii algoritmului: Pasul 1: Pentru fiecare caracter nemarcat de la începutul cuvântului, vom marca 2 caractere la sfâr șitul lui. Astfel, în final vom fi pozi ționați la finalul cuvântului w (sau la poziția L / 3, unde L e lungimea totală a șirului de pe bandă). Stările q0 - q5. Pasul 2: Începând de la sfâr șitul cuvântului w, vom marca caracterul curent și ne vom duce dreapta sărind peste caracterele marcate, și vom marca caracterul la care am ajuns dacă el corespunde cu cel de la care am pornit. Astfel verificăm egalitate primelor 2 cuvinte, w și w^R. Stările q6-q9. Pasul 3: Vom verifica egalitatea cuvintelor w și w(de după w^R). Pentru fiecare caracter de la începutul benzii, îl vom marca și vom merge dreapta sărind peste caracterele marcate până când vom ajunge la cele nemarcate(care apar țin lui w de la finalul benzii) și le vom marca. Astfel, dacă ajunge la Blank, atunci avem soluție validă, și ne rămâne doar să
-
Upload
ion-ureche -
Category
Documents
-
view
222 -
download
0
Transcript of Masini Turing problema
8/10/2019 Masini Turing problema
http://slidepdf.com/reader/full/masini-turing-problema 1/2
Tema MT. gr. 234 Ion Ureche. (Problema 22)
Enun : Se dă un cuvânt nevid format cu literele {a,b,c} amestecate.
Să se accepte intrarea dacă este de forma w w^R w (notam cu w^R cuvântul woglindit, R = inversul său / reverse).
Exemplu: Fie w = abcaa, atunci cuvântul de pe bandă abcaaaacbaabcaa Va fi
acceptat.
Ideea de rezolvare: Vom afla unde se termina cuvântul de bază (w) după
care de la capătul lui vom verifica egalitatea cu w^R, din dreapta sa. Apoi vomverifica egalitatea lui w, cu w` (cel de la finalul benzii).
Pa ii algoritmului:
Pasul 1: Pentru fiecare caracter nemarcat de la începutul cuvântului,vom marca 2 caractere la sfâr șitul lui. Astfel, în final vom fi poziționați lafinalul cuvântului w (sau la poziția L / 3, unde L e lungimea totală așirului de pe bandă). Stările q0 - q5.
Pasul 2: Începând de la sfâr șitul cuvântului w, vom marca
caracterul curent și ne vom duce dreapta sărind peste caracterele marcate,
și vom marca caracterul la care am ajuns dacă el corespunde cu cel de la
care am pornit. Astfel verificăm egalitate primelor 2 cuvinte, w și w^R.
Stările q6-q9.
Pasul 3: Vom verifica egalitatea cuvintelor w și w(de după w^R).
Pentru fiecare caracter de la începutul benzii, îl vom marca și vom mergedreapta sărind peste caracterele marcate până când vom ajunge la cele
nemarcate(care apar țin lui w de la finalul benzii) și le vom marca. Astfel,
dacă ajunge la Blank, atunci avem soluție validă, și ne rămâne doar să
8/10/2019 Masini Turing problema
http://slidepdf.com/reader/full/masini-turing-problema 2/2
refacem cuvântul inițial și să ne ducem într-o stare finală. Stările
q10-q14.
Pasul 4: Pornind de la Blank de la finalul benzii, mergem dreapta
până la Blank și refacem șirul inițial(demarcăm caracterele). Stările
q15-q16.
Complexitate Spa
iu: 3 * |W|, unde |W| e lungimea cuvantului care se repeta.Sau C.S = L, unde L e lungimea șirului de pe bandă.
Complexitate Timp:
Pas 1: 2 * (L / 3) * L => O(L2
)Pas 2: 2 * (L / 3) * (2 * L / 3) => O(L2)
Pas 3: 2 * (L / 3) * (2 * L / 3) => O(L2)Pas 4: L => O(L)Complexitatea finală: O(L2)
Graful Ma
inii Turing:
