MühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu


Tyurinq maşınının təsviredilmə üsulları



Yüklə 179,83 Kb.
səhifə34/38
tarix02.01.2022
ölçüsü179,83 Kb.
#38863
1   ...   30   31   32   33   34   35   36   37   38
VER STR VƏ ALQ müh yeni

Tyurinq maşınının təsviredilmə üsulları

Tyurinq maşınının 3 cür təsviredilmə üsulu var:

əmrlərin birləşməsindən;

qraf şəklində;

cədvəl şəklində

Əmrlərin birləşməsindən istifadə etməklə Tyurinq maşınların təsviri

Maşın tərəfindənyerinə yetirilən bütün əmrlər birləşməsinə proqram deyilir.

Tyurinq maşını aşağıdakı şərtlər yerinə yetirilərsə,düzgün sayılır:

- əgər onun xarici və daxili əlifbası verilərsə;

- proqram;

- başlanğıc konfiqurasiya;

- son vəziyyət.

Əmrlər birləşməsini yazmaq üçün aşağıdakı qaydalardan istifadə etmək lazımdır:



  1. alqoritmin ilkin addımına q0 – başlanğıc vəziyyəti uyğunlaşdırılır;

  2. dövrün son addımlarından başlamğıc addımına keçid yerinə yetirməli;

  3. alqoritmin növbəti addımına keçidə yanaşı vəziyyət uyğun gəlir.

  4. Alqoritmin son addımı son vəziyyətə keçiddir.

Misal.0-lar və 1-dən istifadə edərək giriş zəncirinin Tyurinq maşının əmrlər birləşməsinə baxaq.

Tutaq ki, Tyurinq maşını A={0, 1, ε} çoxluöu ilə verilmiş,haradaki,

ε simvolu boş xananı göstərir,idarəedici qurğunun vəziyyətləri

Q = {q0, q1, qz}. Çoxluğu ilə verilmişdir.Əgər ,məsələn başlanğıc konfiqurasiya q0110011 şəklindədirsə,onda sonuncu konfiqurasiya əməliyyatın sonundan sonra qz001100 şəklində olmalıdır.

Bu məsələnin həlli üçün maçın aşağıdakı əmrlər ardıcıllığından istifadə edəcəkdir:

q01 → q00R, q10 → q10L,

q00 → q01R, q11 → q11L,

q0 ε → q1εL, q1ε → qzεR.

Standart başlanğıc konfiqurasiya başlıq soldakı ilk simvolun üzərindədir və idarəedici qurğu başlanğıc vəziyyətdədir.

Növbəti addımda (taktda) Tyurinq maşını öz vəziyyətini dəyişmədən 0-ı 1-lə və ya 1-i 0-la əvəz edir və sağa 1 simvol sürüşür.Bütün zəncir nəzərdən keçirilərək başlığın altında boş xananı göstərən simvol olur.Bu zaman Tyurinq maşını yeni vəziyyətə keçir və sola 1 simvol sürüşür.Növbəti taktlarda idarəedici qurğu öz vəziyyətini dəyişmir,başlıq altındakı simvolu dəyişməz saxlayır və boş xanaya rast gələnə kimi sola sürüşdürülür.Boş xanaya rast gələrkən Tyurinq maşını sonuncu vəziyyətə keçir və standart sonuncu konfiqurasuyaya keçir.




Yüklə 179,83 Kb.

Dostları ilə paylaş:
1   ...   30   31   32   33   34   35   36   37   38




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin