Tiuringo mašinos. Laboratorinis namų darbas

PIRMOJI UŽDUOTIS

Pradiniai duomenys: juosta, kurioje užrašytos ir tarpu atskirtos dvi sekos: pirmoji iš skaičių,

antroji – iš raidžių, Γ = Σ{ 1, 2, 3, x, y, z, [, ] } ∪ { _ }; pradinė galvutės pozicija yra kairiausias

simbolis. Parašykite Tiuringo mašiną, kuri sukeistų sekas vietomis. Rezultatas turi būti

užrašytas toje pačioje vietoje.

0 [ * r 0 ; Pradinė būsena. Praleidžia bet kokius simbolius iki pirmos sekos pradžios.

0 * * r 0 ; Ignoruoja tarpus ir juda į dešinę iki pirmojo skaičiaus.

Būsenų Veiksmai:

0 1 x r 1 ; Kai aptinkamas skaičius 1, jis pakeičiamas į x ir mašina pereina į būseną 1

0 2 x r 2 ; Kai aptinkamas skaičius 2, jis pakeičiamas į x ir mašina pereina į būseną 2

0 3 x r 3 ; Kai aptinkamas skaičius 3, jis pakeičiamas į x ir mašina pereina į būseną 3

0 a x r a ; Kai aptinkama raidė a, ji pakeičiama į x ir mašina pereina į būseną a

0 b x r b ; Kai aptinkama raidė b, ji pakeičiama į x ir mašina pereina į būseną b

0 c x r c ; Kai aptinkama raidė c, ji pakeičiama į x ir mašina pereina į būseną c

0 _ * * halt ; Jei aptinkama tuščia vieta _, programa baigiasi.

Būsenų Veiksmai:

1 * * r 1 ; Praleidžia simbolius ir juda į dešinę, kol suranda sekos pabaigą

1 _ * r 1 ; Ignoruoja tarpus esančius prieš sekos galą ir juda į dešinę

1 a 1 L a ; Kai aptinkama a, mašina grįžta į kairę

1 b 1 L b ; Kai aptinkama b, mašina grįžta į kairę

1 c 1 L c ; Kai aptinkama c, mašina grįžta į kairę.

2 * * r 2 ; Praleidžia simbolius ir juda į dešinę, kol suranda sekos pabaigą.

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!