Algoritmu teorija - 3.mājas darbs

1. Tjūringa mašīnas darbības laiks. Apskatām šādu skaitļošanas problēmu L: L(x)=1, ja
ieejas virkne x ir formā y#y, kur y ir simbolu virkne, kas sastāv no simboliem a un b. Šī
Tjūringa mašīna darbojas šādi: Atkārto darbību virkni: i. Virzoties pa labi, atrod
pirmo simbolu, kas nav *; ii. Ja pirmais simbols ir a vai b, tad: a. iegaumē šo simbolu
un aizstāj to ar *; b. virzās pa labi līdz # un tad pa labi līdz pirmajam simbolam pēc #,
kas nav *; c. ja tas ir a vai b un sakrīt ar iegaumēto simbolu, tad aizstāj to ar * un virzās
pa kreisi līdz tukšumam pirms ieejas virknes sākuma, tad vienu soli pa labi uz ieejas
virknes pirmo simbolu; d. citādi pāriet uz noraidošo stāvokli. iii. Ja pirmais simbols ir
#, iet pa labi līdz pirmajam simbolam, kas nav *. Ja tāds tiek atrasts, tad iet uz
noraidošo stāvokli. Ja tiek sasniegtas vārda beigas, iet uz akceptējošo stāvokli. Novērtēt
šīs Tjūringa mašīnas darba laiku. Pietiek ar novērtējumu “Laiks ir O(f(n))”, kur f(n) ir
kaut kāda sarežģītības funkcija (piemēram, f(n)=n vai n2 ), bet tas jāpamato.
i)-> simbols, kas nav *
ii)a vai b
a) iegaumē a vai b un *
b) ->#-> līdz simbolam, kas nav *
c) Ja tas ir a vai b(skat. a) punktu ), tad * un <- līdz_ , tad 1.simbols ->
d) qRej
iii)Ja 1. simbols # tad -> līdz x=/*
e) Ja atrod x=/*, tad qRej
f) Citādi qAccept…