Turing-gépes feladat

Közösségi kerekasztal

Üdv!

Holnap írok számításelméletből ZH-t, és a Turing-gépek gyakorlásánál meggyűlt a bajom egy példával:
A feladat egy olyan egyszalagos determinisztikus Turing-gép konstruálása, amely a következő nyelvet fogadja el:
L = {w | w = u#v, u,v e {a,b}* és 2l(u) = l(v)}. Tehát a nyelvben olyan szavak vannak, amelyben van pontosan 1 db # jel, és a #-től jobbra 2-szer annyi betű van, mint a #-től balra.

A problémám az, hogy nem tudom hogyan csináljam ezt meg 1 db szalagon. Eddig azt az algoritmust találtam ki, hogy elmegyek a fejjel egészen a #-ig, majd utána minden 2. betűt kitörlöm(kezdve az elsővel), amikor elértem a végére, akkor elindulok balra, és ha egy betűt olvasok, akkor azt átírom az eggyel balra lévő üres helyre, mindezt a #-ig
Pl.:
ab#abaa => ab#_b_a => ab#ba => ??? Itt hogyan ellenőrzöm le a végén, hogy a # jel mindkét oldalán ugyanannyi betű van?
2 szalagosan meg tudnám oldani, de ez az egyszalagos verzió kifogott rajtam, lehet hogy teljesen rossz irányba indultam el?

A válaszokat előre is köszi :)

  • 2659 megtekintés

( bervi | 2010. 12. 12., v – 21:23 )

ha törölsz, akkor nem fogod tudni, hogy most ez törölt, vagy már a szalag vége, úgyhogy inkább írd át pl. c-re. de ne így, hanem úgy, hogy először a # előtt egyet, aztán a # után kettőt. ha egyszerre fogynak el az a-k és b-k mindkét oldalon, akkor jó vagy. hogy a # előtt vagy, azt nyilván állapottal jelzed.

szerk: a duplatörlésre szintén állapotokat használhatsz.

( zozi56 | 2010. 12. 12., v – 21:15 )

"és ha egy betűt olvasok, akkor azt átírom az eggyel balra lévő üres helyre, mindezt a #-ig"

Ez szerintem nem úgy működik, ahogy gondolod. Ezt csinálja:
ab#_b_a => ab#b_a

Szerintem egyszerűbb, ha először megkétszerezed az első szót:

ab#abaa => ac#abaa => xac#abaa => xcc#abaa => xxcc#abaa

Utána pedig ezzel analóg módon a két szót a szélek felől elfogyasztod.

hát akkor én simán használnám. persze lehet, hogy a ti tanárotok úgy van vele, hogy "tudhatnátok, hogy nem lehet használni", szóval passz. máshogy nem nagyon lehet értelmesen megoldani szerintem. max lehet a részszavakat tologatni (tehát egyet törölsz, aztán minden balrább kerül, aztán kettőt a # után, aztán megint tologatás), de az nagyon lassú.

Esetleg lehetne valami olyasmit, hogy kezdetben elmegyek #-ig, majd utána 2-t átírok #-re, utána elindulok a másik irányba, és amint betűt olvasok, átírok egyet #-re, majd elindulok vissza stb. És amikor elérek az egyik végére, és már nincs betű, majd átmegyek a másik végére, és ott sincs betű akkor kész. Bár egyelőre nem tudom, hogy ez megvalósítható-e.

"végigtologatja az egész szalagot"

Akkor lehet, hogy nem sikerült elég jól leírnom, mire gondoltam. Tologatás nincs a duplázó szakaszban, csak egy n hosszú kifejezés átírása (x^n c^n) alakúra. Ez pedig szerintem legfeljebb négyzetes (ha minden esetben, mikor az első c-t keresi egy x kiírása után, visszamenne #-ig, azon jobban látszik, miért), és a második (az ellenőrző) szakasz is az.

Ettől függetlenül persze a tiéd hatékonyabb, de nem nagyságrendileg.

turing-gépnél nincs olyan, hogy "átírod" hosszabbra, ez nem láncolt lista, hogy csak úgy közészúrt valamit, csak celláid vannak. ha közé akarsz valamit beszúrni, akkor minden utána lévő cellát egyesével át kell másolgatni a jobbra levőbe, nyilván a végénél kezdve. jelen esetben ezt n/4-szer kellene végigzongorázni, szóval nagyjából (n/4)*(n/2), ha jól számolom, magyarul (n^2)/2, és akkor még semmit nem ellenőriztünk, csak csinosítottunk az inputszón.

a kérdés már csak az, hogy az ellenőrzés az valóban négyzetes-e, amit még át kell gondoljak. ha az, akkor nagyságrendileg tényleg nem növeli, csak mondjuk (hasraütésre) 2-szeres lesz a lefutási idő. ha nem négyzetes, akkor viszont ront rajta.

egyáltalán nem nyilvánvaló!

ha a géped egy traktor és csak egy bites gödrök/földkupacok a jelek akkor a jelekhez csak plus egy állapot kell és a trakor meg nehezen mozog végig a szallagon, nem tudom láttál-e szallagos egységet vagy stdin-t:)

ha persze nagy az abc és drága az állapot, akkor tényleg nyilvánvaló

nem értem az egy beszúrást*, nem puffer állapotot használunk hanem az az egy állapot hogy "és akkor mpost lépkedünk a végéig" bomlik fel abc méretű részállapotokra, hogy "éppen mit töröltünk és kell majd a következőbe beírni"

egyébként pont annyira részletkérdés mint a turing gép hatékonyságáról beszélni ;) de ha hatékonyságról van szó akkor _kell_ definiálni hogy minek mennyi a költsége

*: megvan, nem a szálon gondolkoztam csak a beszúráson :)

"turing-gépnél nincs olyan, hogy "átírod" hosszabbra, ez nem láncolt lista, hogy csak úgy közészúrt valamit, csak celláid vannak."
Nincs, nyilvánvalóan, ez csak rövidítés volt részemről. Gondoltam, triviális egy karaktersorozatból négyzetes időben előállítani egy kétszer akkorát, ami "balra lóg túl" az eredetin.