Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar. Amaliy mashg’ulot. Mavzu

QURILMA DASTURI

Turing mexanizmi uchun dasturlar jadvallar bilan formatlangan bo'lib, unda birinchi qator va ustun tashqi alifbo belgilarini va mashinaning mumkin bo'lgan ichki holatining qiymatlarini - ichki alifboni o'z ichiga oladi. Jadvalli ma'lumotlar Turing mashinasi tomonidan qabul qilinadigan buyruqlardir. Muammolarning yechimi quyidagicha: hujayradagi bosh tomonidan o'qilgan xat, u yuqorida joylashgan bu daqiqa topiladi va mashina boshining ichki holati buyruqlarning qaysi biri bajarilishi kerakligini belgilaydi. Xususan, bunday buyruq jadvaldagi tashqi va ichki alifbo belgilarining kesishgan joyida joylashgan.

HISOBLASH KOMPONENTLARI

Bitta aniq muammoni hal qilish uchun Tyuring mashinasini qurish uchun uning quyidagi parametrlarini aniqlash kerak.
Tashqi alifbo. Bu A belgisi bilan belgilanadigan, tashkil etuvchi elementlari harflar bilan ataladigan ba'zi chekli belgilar to'plami. Ulardan biri - a0 - bo'sh bo'lishi kerak. Masalan, Tyuring qurilmasi bilan ishlaydigan alifbo ikkilik raqamlar, quyidagicha ko'rinadi: A = (0, 1, a0).
Lentaga yozib olingan harf-ramzlarning uzilmagan qatori so'z deyiladi.
Avtomat - bu inson aralashuvisiz ishlaydigan qurilma. Turing mashinasida u muammolarni hal qilish uchun bir necha xil holatlarga ega va yuzaga keladigan muayyan sharoitlarda bir pozitsiyadan ikkinchisiga o'tadi. Bunday tashish holatlarining to'plami ichki alifbodir. U Q = (q1, q2 ...) ko'rinishidagi harf belgisiga ega. Ushbu pozitsiyalardan biri - q1 - boshlang'ich bo'lishi kerak, ya'ni dasturni ishga tushiradigan narsa. Yana bir zarur element - bu yakuniy, ya'ni dasturni tugatuvchi va qurilmani to'xtash holatiga keltiradigan holat q0.
O'tish stoli. Ushbu komponent mashinaning holati va hozirgi vaqtda o'qilayotgan belgining qiymatiga qarab, qurilma vagonining xatti-harakati uchun algoritmdir.

AVTOMAT UCHUN ALGORITM

Turing qurilmasining ish paytida tashish dasturi har bir bosqichda quyidagi harakatlar ketma-ketligini bajaradigan dastur tomonidan boshqariladi:

1. 
   Tashqi alifbo belgisini pozitsiyaga, shu jumladan bo'shga yozish, undagi elementni, shu jumladan bo'shni almashtirish.
   
2. 
   Bir katakchani chapga yoki o'ngga siljiting.
   
3. 
   Sizning ichki holatingizni o'zgartirish.
   

Shunday qilib, har bir juft belgilar yoki pozitsiyalar uchun dasturlarni yozishda uchta parametrni aniq tasvirlash kerak: ai - tanlangan A alifbosidan element, vagonning siljish yo'nalishi ("←" chapga, "→" o'ng, "nuqta" - harakat yo'q) va qk - qurilmaning yangi holati Masalan, 1 "←" q 2 buyrug'i "belgini 1 ga almashtiring, vagon boshini chapga bir katak qadamiga o'tkazing va bajaring. q 2" holatiga o'tish.